萌新初学OI,求助

@Sai_0511 2019-04-19 22:43 回复

谁告诉我哪里写错了呀qwq?

#include <bits/stdc++.h>
#define il inline     
const int maxn = 4e5 + 10;
const int mod = 998244353;
using namespace std;     
int f[maxn],g[maxn];        
int n,m,i,j,k;   
il void _swap(int& x,int& y) {
    int t = x;  x = y;  y = t;
    return;
}
il int mul(int a,int b) {
    return 1ll * a * b % mod;
}
il int ins(int a,int b) {
    a += b;  if(a > mod) a -= mod;  return a;
}
il int sub(int a,int b) {
    a -= b;  if(a < 0) a += b;  return a;
}
il int qpow(int a,int b,int p = mod) {
    int res = 1;
    while(b) {
        if(b & 1) res = mul(res,a);
        a = mul(a,a);  b >>= 1;
    }
    return res;
}
namespace Poly_Space {
    int rev[maxn],A[maxn],B[maxn],tmp[maxn],C[maxn],D[maxn];   
    il void ntt(int* p,int lim,int type) {
        int li = 1, tot = 0;
        while(li < lim) li <<= 1, tot++;  
        for(int i = 0;i < li;i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (tot - 1));
        for(int i = 0;i < li;i++) if(i < rev[i]) _swap(p[i],p[rev[i]]);
        for(int i = 1;i < li;i <<= 1) {
            int wn = qpow(3,(mod - 1) / (i << 1));  tmp[0] = 1;  
            for(int j = 1;j < i;j++) tmp[j] = mul(tmp[j - 1],wn);
            for(int j = 0;j < li;j += i << 1) {
                for(int k = 0;k < i;k++) {
                    int x = p[j + k], y = mul(tmp[k],p[j + k + i]);
                    p[j + k] = ins(x,y);  p[j + k + i] = sub(x,y);    
                }
            }
        }
        if(!~type) {
            reverse(p + 1,p + li);  int inv = qpow(lim,mod - 2);
            for(int i = 0;i < li;i++) p[i] = mul(p[i],inv);  
        }
        return;
    }
    void Poly_Inv(int* a,int* b,int deg) {
        if(deg == 1) return void(b[0] = qpow(a[0],mod - 2));
        Poly_Inv(a,b,deg >> 1);  
        for(int i = 0;i < deg;i++) A[i] = a[i], B[i] = b[i];
        ntt(A,deg << 1,1);  ntt(B,deg << 1,1);
        for(int i = 0;i < deg << 1;i++) A[i] = mul(mul(A[i],B[i]),B[i]);
        ntt(A,deg << 1,-1);  
        for(int i = 0;i < deg;i++) b[i] = sub(1ll * (b[i] << 1) % mod,A[i]);
        return;
    }
    il void direv(int* a,int* b,int li) {
        for(int i = 1;i < li;i++) b[i - 1] = mul(a[i],i);  b[li - 1] = 0;
    }
    il void integ(int* a,int* b,int li) {
        for(int i = 1;i < li;i++) b[i] = mul(a[i - 1],qpow(i,mod - 2));  b[0] = 0;  
    }
    il void Poly_Ln(int* a,int* b,int li) {
        direv(a,C,li);  Poly_Inv(a,D,li);  
        ntt(C,li << 1,1);  ntt(D,li << 1,1);
        for(int i = 0;i < li << 1;i++) C[i] = mul(C[i],D[i]);
        ntt(C,li << 1,-1);  integ(C,b,li);    
    }
}
using namespace Poly_Space;
int main() {
    scanf("%d",&n);
    for(int i = 0;i < n;i++) scanf("%d",&f[i]);
    int li = 1;  while(li < n) li <<= 1;
    Poly_Ln(f,g,li);
    for(int i = 0;i < n;i++) printf("%d ",g[i]);
    return 0;
}
@Irressey 2019-04-19 22:51 回复 举报

好吧我们的写法似乎不一样

但我记得求逆一开始的deg是原长度

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。