HDU-6061 RXD and functions (NTT)
HDU-6061(NTT)
题意：给定\(f(x)\)求\(f(x-t)\)，系数对于\(998244353\)取模
其实本质依然是一个构造卷积
\[f(x)=\sum a_ix^i \]\[f(x-t)=\sum a_i(x-t)^i \]\((x-t)^i\)我们可以直接暴力用二项式定理展开，得到\(f(x-t)=\sum a_iC(i,j)t^{i-j}x^j\)
考虑每个\(i\)对于每个\(j\)的贡献，是一个组合数形式的，即\(\frac{i!}{j!(i-j)!}\)可以看到和差有关，所以可以卷积
对于初始的序列乘上\(i!\)，转移序列为\(\frac{t^{i-j}}{(i-j)!}\)，最终得到的序列再乘上一个\(\frac{1}{j!}\)即可
#include
using namespace std;
//#define double long double
#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)
template inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template inline void cmax(T &a,T b){ ((a>=1,x=x*x%P) if(k&1) res=res*x%P;
return res;
}
void NTT(int n,ll *a,int f){
rep(i,0,n-1) if(i>1]>>1)|((i&1)<