天天看點
傳回

[帶标号DAG計數 容斥原理 多項式求逆 多項式求ln] COGS 有标号的DAG計數系列

題目連結 傳送門I 傳送門II 傳送門III 傳送門IV

題解戳這裡

大緻解法和思想是同這裡一樣的

DAG1

找出一個入度為 0 的點 那麼答案為C1n∗21∗(n−1)∗fn−1 但是一張DAG裡會有多個入度為 0 的點會重複計數

考慮容斥 得到

fn=∑k=1n(−1)k−1∗Ckn∗2k∗(n−k)∗fn−k

直接遞推求解

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N=;
const int P=;
const int Root2=;

inline int Pow(int a,int b){
  int ret=; for (;b;b>>=,a=a*a%P) if (b&) ret=ret*a%P; return ret;
}

int _pow[P],C[N][N];
inline void Pre(){
  C[][]=;
  for (int i=;i<=;i++){
    C[i][]=;
    for (int j=;j<=i;j++)
      C[i][j]=(C[i-][j-]+C[i-][j])%P;
  }
  _pow[]=;
  for (int i=;i<P;i++) _pow[i]=_pow[i-]*%P;
}

int n;
ll f[N];

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  scanf("%d",&n); Pre();
  f[]=;
  for (int i=;i<=n;i++){
    for (int j=;j<=i;j++){
      int tmp=(ll)C[i][j]*_pow[j*(i-j)%(P-)]*f[i-j]%P;
      if (j&) f[i]+=tmp; else f[i]-=tmp;
    }
    f[i]=(f[i]%P+P)%P;
  }
  printf("%d\n",f[n]);
  return ;
}

DAG2

考慮如何拆分 2k∗(n−k)

2k∗(n−k)=2n222k22∗2(n−k)22

這裡我們需要求 2 的二次剩餘

那麼把DAG1中的柿子改為分治FFT或多項式求逆就可以了

但是在DAG1中不能這麼做 因為模數不對 汗

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N=;
const int P=;
const int G=; const int Root2=;

inline int Pow(ll a,int b){
  ll ret=; for (;b;b>>=,a=a*a%P) if (b&) ret=ret*a%P; return ret;
}

int num;
int w[][N];
ll fac[N],inv[N];

inline void Pre(int n){
  num=n;
  ll g=Pow(G,(P-)/num);
  w[][]=; for (int i=;i<num;i++) w[][i]=g*w[][i-]%P;
  w[][]=; for (int i=;i<num;i++) w[][i]=w[][num-i];
}
int R[N];
inline void FFT(int *a,int n,int r){
  for (int i=;i<n;i++) if (i<R[i]) swap(a[i],a[R[i]]);
  for (int i=;i<n;i<<=)
    for (int j=;j<n;j+=(i<<))
      for (int k=;k<i;k++){
    ll x=a[j+k],y=(ll)w[r][num/(i<<)*k]*a[j+i+k]%P;
    a[j+k]=(x+y)%P; a[j+i+k]=(x+P-y)%P;
      }
  if (!r) for (int i=,inv=Pow(n,P-);i<n;i++) a[i]=(ll)a[i]*inv%P;
}
inline void GetInv(int *a,int *b,int n){
  static int tmp[N];
  if (n==) return void(b[]=Pow(a[],P-));
  GetInv(a,b,n>>);
  for (int i=;i<n;i++) tmp[i]=a[i],tmp[n+i]=;
  int L=; while (!(n>>L&)) L++;
  for (int i=;i<(n<<);i++) R[i]=(R[i>>]>>)|((i&)<<L);
  FFT(tmp,n<<,); FFT(b,n<<,);
  for (int i=;i<(n<<);i++)
    tmp[i]=(ll)b[i]*(+P-(ll)tmp[i]*b[i]%P)%P;
  FFT(tmp,n<<,);
  for (int i=;i<n;i++) b[i]=tmp[i],b[n+i]=;
}

int n,m;
int A[N],B[N];

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  scanf("%d",&n);
  fac[]=; for (int i=;i<=n;i++) fac[i]=fac[i-]*i%P;
  for (m=;m<=n;m<<=); Pre(m<<);
  A[]=;
  for (int i=;i<=n;i++){
    ll tmp=fac[i]*Pow(Root2,(ll)i*i%(P-))%P;
    tmp=Pow(tmp,P-);
    A[i]=i&?P-tmp:tmp;
  }
  GetInv(A,B,m);
  int Ans=fac[n]*B[n]%P*Pow(Root2,(ll)n*n%(P-))%P;
  printf("%d\n",Ans);
  return ;
}

DAG3

設fn為 n 個點的DAG的個數

設gn為 n 個點的連通DAG的個數

容斥的柿子

gn=fn−∑k=1n−1Ck−1n−1∗gk∗fn−k

大力遞推

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N=;
const int P=;
const int Root2=;

inline int Pow(int a,int b){
  int ret=; for (;b;b>>=,a=a*a%P) if (b&) ret=ret*a%P; return ret;
}

int _pow[P],C[N][N];
inline void Pre(){
  C[][]=;
  for (int i=;i<=;i++){
    C[i][]=;
    for (int j=;j<=i;j++)
      C[i][j]=(C[i-][j-]+C[i-][j])%P;
  }
  _pow[]=;
  for (int i=;i<P;i++) _pow[i]=_pow[i-]*2%P;
}

int n;
ll f[N],g[N];

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  scanf("%d",&n); Pre();
  f[]=;
  for (int i=;i<=n;i++){
    for (int j=;j<=i;j++){
      int tmp=(ll)C[i][j]*_pow[j*(i-j)%(P-)]*f[i-j]%P;
      if (j&) f[i]+=tmp; else f[i]-=tmp;
    }
    f[i]=(f[i]%P+P)%P;
  }
  for (int i=;i<=n;i++){
    g[i]=f[i];
    for (int j=;j<i;j++)
      g[i]-=(ll)C[i-][j-]*g[j]*f[i-j];
    g[i]=(g[i]%P+P)%P;
  }
  printf("%d\n",g[n]);
  return ;
}

DAG4

不論是由容斥的柿子還是多項式exp ln的組合意義都不難得出多項式的做法

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define cl(x) memset(x,0,sizeof(x))
using namespace std;
typedef long long ll;

const int N=;
const int P=;
const int G=; const int Root2=;

inline int Pow(ll a,int b){
  ll ret=; for (;b;b>>=,a=a*a%P) if (b&) ret=ret*a%P; return ret;
}

int num;
int w[][N];
ll fac[N],inv[N];

inline void Pre(int n){
  num=n;
  ll g=Pow(G,(P-)/num);
  w[][]=; for (int i=;i<num;i++) w[][i]=g*w[][i-]%P;
  w[][]=; for (int i=;i<num;i++) w[][i]=w[][num-i];
}
int R[N];
inline void FFT(int *a,int n,int r){
  for (int i=;i<n;i++) if (i<R[i]) swap(a[i],a[R[i]]);
  for (int i=;i<n;i<<=)
    for (int j=;j<n;j+=(i<<))
      for (int k=;k<i;k++){
    ll x=a[j+k],y=(ll)w[r][num/(i<<)*k]*a[j+i+k]%P;
    a[j+k]=(x+y)%P; a[j+i+k]=(x+P-y)%P;
      }
  if (!r) for (int i=,inv=Pow(n,P-);i<n;i++) a[i]=(ll)a[i]*inv%P;
}
inline void GetInv(int *a,int *b,int n){
  static int tmp[N];
  if (n==) return void(b[]=Pow(a[],P-));
  GetInv(a,b,n>>);
  for (int i=;i<n;i++) tmp[i]=a[i],tmp[n+i]=;
  int L=; while (!(n>>L&)) L++;
  for (int i=;i<(n<<);i++) R[i]=(R[i>>]>>)|((i&)<<L);
  FFT(tmp,n<<,); FFT(b,n<<,);
  for (int i=;i<(n<<);i++)
    tmp[i]=(ll)b[i]*(+P-(ll)tmp[i]*b[i]%P)%P;
  FFT(tmp,n<<,);
  for (int i=;i<n;i++) b[i]=tmp[i],b[n+i]=;
}

int n,m,F[N];
int A[N],B[N],invB[N];

inline void Calc(){
  A[]=;
  for (int i=;i<=n;i++){
    ll tmp=fac[i]*Pow(Root2,(ll)i*i%(P-))%P;
    tmp=Pow(tmp,P-);
    A[i]=i&?P-tmp:tmp;
  }
  cl(B); GetInv(A,B,m);
  for (int i=;i<=n;i++)
    F[i]=fac[i]*B[i]%P*Pow(Root2,(ll)i*i%(P-))%P;
}

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  scanf("%d",&n);
  fac[]=; for (int i=;i<=n;i++) fac[i]=fac[i-]*i%P;
  inv[]=; for (int i=;i<=n;i++) inv[i]=inv[P%i]*(P-P/i)%P;
  inv[]=; for (int i=;i<=n;i++) inv[i]=(inv[i]*inv[i-])%P;
  for (m=;m<=n;m<<=); Pre(m<<);
  Calc();
  cl(A); cl(B);
  for (int i=;i<=n;i++) A[i]=F[i]*inv[i-]%P;
  for (int i=;i<=n;i++) B[i]=F[i]*inv[i]%P;
  GetInv(B,invB,m);
  FFT(A,m<<,); FFT(invB,m<<,);
  for (int i=;i<(m<<);i++) A[i]=(ll)A[i]*invB[i]%P;
  FFT(A,m<<,);
  printf("%d\n",(ll)A[n]*fac[n-]%P);
  return ;
}
多項式
上一篇: 【探索 Kubernetes|容器基礎進階篇 系列1】容器的本質是程序
下一篇: 多項式求逆與多項式開根

繼續閱讀