本文共 1113 字，大约阅读时间需要 3 分钟。
#include #include #include #include #include #include #include #include #include using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=500010,Mod=1004535809,G=3;int r[N],fac[10000010],n,m,s,W[N],a[N],b[N];int qpow(int a,int b){int ret=1;while(b){if(b&1)ret=(ll)ret*a%Mod;a=(ll)a*a%Mod;b>>=1;}return ret;}void NTT(int limit,int type,int *A){ for(int i=0;i >1]>>1)|((i&1)<<(l-1)); for(int i=0;i<=lim;i++) a[i]=(ll)fac[i]*C(m,i)%Mod*fac[n]%Mod*qpow(m-i,n-i*s)%Mod*qpow((1ll*fac[n-i*s]*qpow(fac[s],i)%Mod),Mod-2)%Mod; for(int i=0;i<=lim;i++) { b[i]=qpow(fac[lim-i],Mod-2); if((lim-i)&1)b[i]=Mod-b[i]; } NTT(limit,1,a); NTT(limit,1,b); for(int i=0;i
转载于:https://www.cnblogs.com/mle-world/p/10330911.html