数论
5-02 PN筛
7-09 min-25 插值
多项式
7-10 EGF
题目链接
对于有标号的计数问题，考虑EGF，且有已知结论：设无向图的EGF为G，无向连通图的EGF为F，有G=exp(F)。
考虑边出现的概率如何处理：即要满足两个无向连通图在合并的时候，它们之间的边都不存在。那么参照EGF处理组合数的思路，先把每项除掉\((1-p)^{C(n,2)}\)，最后乘回去即可。
然后考虑计算答案：\(ans=\sum{[x^n]F^i\times \frac{i}{i!}}\)，注意这里除以\(i!\)的意义是：对于每种本质不同的方案，\(i\)个连通块在原来逐渐合并，标号的过程中，有\(i!\)种分配点的方式。
那么容易根据结论化为\(ans=\sum{[x^n]GLn(G)}\)
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20)+5,P=998244353,G[2]={3,(P+1)/3};
int rv[N],gp[2][N],iv[N];
void print(char name[],int n,int* a){
printf("%s n=%d\n",name,n);
for(int i=0;i<n;i++) cout<<a[i]<<" "; puts("");
}
inline int fpw(int a,int x){
int s=1;
for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
return s;
}
inline void dft(int* a,int n,int p){
for(int i=0;i<n;i++) if(i<rv[i]) swap(a[i],a[rv[i]]);
for(int i=1;i<n;i<<=1){
for(int j=0;j<n;j+=(i<<1)){
for(int k=0;k<i;k++){
int &A=a[i+j+k],&B=a[j+k],t=1ll*gp[p][i+k]*A%P;
A=B-t; if(A<0) A+=P;
B=B+t; if(B>=P) B-=P;
}
}
}
if(p) for(int i=0;i<n;i++) a[i]=1ll*a[i]*iv[n]%P;
}
inline int Rev(int m){
int p=0,n=1;
while(n<m) n<<=1,p++;
for(int i=0;i<n;i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(p-1));
return n;
}
inline void poly_mul(int m,int* A,int* B,int* C){
int n=Rev(m);
dft(A,n,0); dft(B,n,0);
for(int i=0;i<n;i++) C[i]=1ll*A[i]*B[i]%P;
dft(C,n,1);
fill(C+m,C+n,0);
}
//C=A*B m:需要C的0~(m-1)项,m~(n-1)为空
int C[N];
inline void poly_inv(int n,int *a, int *b) {
if (n == 1) {
b[0] = fpw(a[0],P-2);
return;
}
poly_inv((n + 1) >> 1, a, b);
int len=Rev(n << 1);
copy(a, a + n, C);
fill(C + n, C + len, 0);
dft(b,len,0); dft(C,len,0);
for (int i = 0; i < len; ++i) {
b[i]=1ll*b[i]*(P+2-1ll*b[i]*C[i]%P)%P;
}
dft(b,len,1);
fill(b + n, b + len, 0);
}
//a*b=1,给定a的0~(n-1)项，返回b的0~(n-1)项
//需要保证初始b为空!
inline void poly_Ln(int m,int* a,int* b){
poly_inv(m,a,b);
for(int i=0;i<m-1;i++) C[i]=1ll*a[i+1]*(i+1)%P; C[m-1]=0;
int n=Rev(m<<1);
fill(C+m,C+n,0);
dft(C,n,0); dft(b,n,0);
for(int i=0;i<n;i++) b[i]=1ll*C[i]*b[i]%P;
dft(b,n,1);
for(int i=m-1;i;i--) b[i]=1ll*b[i-1]*iv[i]%P; b[0]=0;
fill(b+m,b+n,0);
}
int fc[N],fv[N];
void init(){
int n=(1<<20);
fc[0]=1;
for(int i=1;i<n;i++) iv[i]=fpw(i,P-2),fc[i]=1ll*fc[i-1]*i%P;
fv[n-1]=fpw(fc[n-1],P-2);
for(int i=n-2;~i;i--) fv[i]=1ll*fv[i+1]*(i+1)%P;
for(int p=0;p<2;p++){
for(int i=1;i<n;i<<=1){
gp[p][i]=1;
int t=fpw(G[p],(P-1)/(i<<1));
for(int j=i+1;j<(i<<1);j++) gp[p][j]=1ll*gp[p][j-1]*t%P;
}
}
}
int A[N],B[N],qy[N];
int main()
{
init();
int T; cin>>T;
while(T--){
int q,a,b,p,ip,n=0;
cin>>q>>a>>b;
p=(P+1-1ll*a*fpw(b,P-2)%P)%P;
ip=fpw(p,P-2);
for(int i=1;i<=q;i++) scanf("%d",&qy[i]),n=max(n,qy[i]);
A[0]=1;
for(int i=1;i<=n;i++) A[i]=1ll*fv[i]*fpw(ip,1ll*i*(i-1)/2%(P-1))%P;
poly_Ln(n+1,A,B);
int m=Rev((n+1)<<1);
dft(A,m,0); dft(B,m,0);
for(int i=0;i<m;i++) A[i]=1ll*A[i]*B[i]%P;
dft(A,m,1);
for(int i=1;i<=q;i++){
int n=qy[i],s=1ll*fc[n]*fpw(p,1ll*n*(n-1)/2%(P-1))%P*A[n]%P;
if(i>1) printf(" ");
printf("%d",s);
}
puts("");
for(int i=0;i<m;i++) A[i]=B[i]=0;
}
return 0;
}
8-13 求逆
其实是很大力的容斥，直接DP计算每个位置第一次出现排列的方案数，化成多项式形式之后可以求逆计算。
#include<bits/stdc++.h>
using namespace std;
const int N=(1<<20),P=998244353,G[2]={3,(P+1)/3};
int rv[N],gp[2][N],iv[N];
inline int fpw(int a,int x){
int s=1;
for(;x;x>>=1,a=1ll*a*a%P) if(x&1) s=1ll*s*a%P;
return s;
}
inline void dft(int* a,int n,int p){
//cout<<n<<endl;
for(int i=0;i<n;i++) if(i<rv[i]) swap(a[i],a[rv[i]]);
for(int i=1;i<n;i<<=1){
//int wn=gp[p][i];
for(int j=0;j<n;j+=(i<<1)){
//int w=1;
for(int k=0;k<i;k++){
int &A=a[i+j+k],&B=a[j+k],t=1ll*gp[p][i+k]*A%P;
A=B-t; if(A<0) A+=P;
B=B+t; if(B>=P) B-=P;
}
}
}
if(p) for(int i=0;i<n;i++) a[i]=1ll*a[i]*iv[n]%P;
}
int Rev(int m){
int p=0,n=1;
while(n<=m) n<<=1,p++;
for(int i=0;i<n;i++) rv[i]=(rv[i>>1]>>1)|((i&1)<<(p-1));
return n;
}
inline int poly_mul(int m,int* A,int* B,int* C){
int n=Rev(m);
dft(A,n,0); dft(B,n,0);
for(int i=0;i<n;i++) C[i]=1ll*A[i]*B[i]%P;
dft(C,n,1);
return n;
}
//C=A*B m:需要C的0-(m-1)项 n:返回C的项数
int C[N];
inline void poly_inv(int n,int *a, int *b) {
if (n == 1) {
b[0] = fpw(a[0],P-2);
return;
}
poly_inv((n + 1) >> 1, a, b);
int len=Rev(n << 1);
copy(a, a + n, C);
fill(C + n, C + len, 0);
//fill(b + ((n + 1)>>1), b + len, 0);
dft(b,len,0); dft(C,len,0);
for (int i = 0; i < len; ++i) {
//b[i] = Mul(Sub(2, Mul(b[i], C[i])), b[i]);
b[i]=1ll*b[i]*(P+2-1ll*b[i]*C[i]%P)%P;
}
dft(b,len,1);
fill(b + n, b + len, 0);
}
void init(){
for(int i=1;i<N;i++) iv[i]=fpw(i,P-2);
for(int p=0;p<2;p++){
for(int i=1;i<N;i<<=1){
gp[p][i]=1;
int t=fpw(G[p],(P-1)/(i<<1));
for(int j=i+1;j<(i<<1);j++) gp[p][j]=1ll*gp[p][j-1]*t%P;
}
}
}
int n,m,pn[N],fc[N],A[N],B[N],iB[N],f[N];
int main()
{
init();
int T; cin>>T;
while(T--){
cin>>n>>m;
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
memset(iB,0,sizeof(iB));
pn[0]=fc[0]=1;
for(int i=1;i<=m;i++) pn[i]=1ll*pn[i-1]*n%P,fc[i]=1ll*fc[i-1]*i%P;
int k=m-n+1;
for(int i=0;i<=k;i++){
if(!i) A[i]=0;
else A[i]=1ll*pn[i-1]*fc[n]%P;
if(!i) B[i]=1;
if(i>=n) (B[i]+=1ll*pn[i-n]*fc[n]%P)%=P;
if(i && i<n) (B[i]+=fc[i])%=P;
}
poly_inv(k+1,B,iB);
poly_mul(k+1+k+1,A,iB,f);
int s=0;
for(int i=1;i<=k;i++) (s+=1ll*f[i]*pn[m-i-n+1]%P)%=P;
//cout<<pn[m]<<" "<<s<<endl;
cout<<(pn[m]+P-s)%P<<endl;
}
return 0;
}