COGS2353 【HZOI2015】有标号的DAG计数 I
2024-09-04 23:32:01
题面
题目描述
给定一正整数n,对n个点有标号的有向无环图(可以不连通)进行计数,输出答案mod 10007的结果
输入格式
一个正整数n
输出格式
一个数,表示答案
样例输入
3
样例输出
25
提示
对于20%的数据:n<=5
对于50%的数据:n<=500
对于100%的数据:1<=n<=5000
题目分析
设\(f(i)\)表示有\(i\)个点构成DAG图
设其中\(j\)个点出度为\(0\),则有:
\[f(i)=\sum_{j=1}^i\binom ij2^{(i-j)\cdot j}\cdot f(i-j)
\]
\]
意思是,在\(i\)个点中选出\(j\)个点有\(\binom ij\)种方案,
在\(i-j\)个点与这\(j\)个点之间随意连边,\(i-j\)个点构成的图仍为DAG的情况数。
但由于无法保证那\(i-j\)个点一定出度不为\(0\),所以需要容斥。
\[f(i)=\sum_{j=1}^i\binom ij2^{(i-j)\cdot j}\cdot f(i-j)\cdot (-1)^{j-1}
\]
\]
代码实现
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef long long LL;
const int N=5005,mod=10007;
using namespace std;
inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}
int f[N],c[N][N];
int ksm(int x,int k){
int ret=1;
while(k){
if(k&1)ret=ret*x%mod;
x=x*x%mod,k>>=1;
}
return ret;
}
int main(){
freopen("DAG.in","r",stdin);
freopen("DAG.out","w",stdout);
int n=Getint();
c[0][0]=f[0]=1;
for(register int i=1;i<=n;c[i++][0]=1){
for(register int j=1;j<=i;++j){
c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
f[i]=(f[i]+c[i][j]*ksm(2,j*(i-j)%(mod-1))%mod*f[i-j]%mod*((j&1)?1:-1)+mod)%mod;
}
}
cout<<f[n];
return 0;
}
最新文章
- Ubuntu安装Hadoop与Spark
- DevExpress Ribbongallerybaritem选择性皮肤重组
- selenium操作H5视频
- LINUX信息安全系统设计基础第一周学习总结
- 超爱http://www.runoob.com/菜鸟编程
- Java基础之读文件——使用通道读取混合数据2(ReadPrimesMixedData2)
- js 数组详解(javascript array)
- Mysql int(11) 和 int(1)
- 使用Cloudsim实现基于多维QoS的资源调度算法之中的一个:配置Cloudsim环境
- Linux防火墙配置—SNAT1
- 通过cmd命令行连接mysql数据库
- Linux基础操作二
- 【ES】学习8-聚合1
- mongodb副本集加分片集群安全认证使用账号密码登录
- C# AOP框架入门(转)
- Tomcat启动之异常java.lang.IllegalStateException
- trmd_b1_ok
- 小鸡G4工程款 上手体验
- CentOS7 minimal(最小化安装)后增加的软件安装
- SpringBoot 集成Mybatis时 使用通用插件Mapper 注意事项