【题解】有标号的DAG计数3

[HZOI 2015] 有标号的DAG计数 III

我们已经知道了\(f_i\)表示不一定需要联通的\(i\)节点的dag方案，考虑合并

参考【题解】P4841 城市规划(指数型母函数+多项式Ln)，然后答案\(h_i\)母函数\(H(x)\)就这样解

由于

\[H(x)=\sum_{i=0}^{\inf} \dfrac {(F(x))^i} {i!}
\]

则

\[H(x)=e^{F(x)}
\]

球\(\ln\)就是IV，不求的话可以直接手动模拟\(F(x)^i/i!\)

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(c<48||c>57)f|=c==45,c=getchar();

      while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=5e3+5;

const int mod=10007;

int c[maxn][maxn];

int dp[maxn];

int f[maxn];

int bin[maxn*maxn];

int main(){

      freopen("DAGIII.in","r",stdin);

      freopen("DAGIII.out","w",stdout);

      int n=qr();

      bin[0]=1;dp[0]=1;

      for(register int t=0;t<=n;++t){

	    c[t][0]=1;

	    for(register int i=1;i<=t;++i){

		  c[t][i]=(c[t-1][i-1]+c[t-1][i])%mod;

	    }

      }

      for(register int t=1;t<=n*n;++t) bin[t]=(bin[t-1]<<1)%mod;

      for(register int t=1;t<=n;++t){

	    for(register int i=1,d;i<=t;++i){

		  d=mod-c[t][i]*bin[i*(t-i)]%mod*dp[t-i]%mod;

		  if(i&1) d=mod-d;

		  dp[t]=(dp[t]+d)%mod;

	    }

      }

      for(register int t=1;t<=n;++t){

	    int d=0;

	    for(register int i=1;i<=t;++i)

		  d=(d+c[t-1][i-1]*f[i]%mod*dp[t-i]%mod)%mod;

	    f[t]=(dp[t]-d+mod)%mod;

      }

      printf("%d\n",f[n]);

      return 0;

}

巴特西

【题解】有标号的DAG计数3

[HZOI 2015] 有标号的DAG计数 III

最新文章

热门文章