1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<string> 5 #include<cstring> 6 #include<algorithm> 7 using namespace std; 8 namespace Moxing{ 9 const int N=1e4+20,lim=1e4; 10 int n,p,mod,fac[N],lim[N]; 11 int mul(int a,int b){ 12 int ans=0; 13 while(b){ 14 if(b&1){ 15 ans=(ans+a)%mod; 16 } 17 b>>=; 18 a=(a+a)%mod; 19 } 20 return ans; 21 } 22 int power(int a,int b){ 23 int ans=1; 24 while(b){ 25 if(b&1){ 26 ans=mul(ans,a); 27 } 28 b>>=1; 29 a=mul(a,a); 30 } 31 return ans; 32 } 33 void first(){ 34 fac[0]=1; 35 for(int i=1;i<=lim;i++){ 36 fac[i]=mul(fac[i-1],i); 37 } 38 inv[lim]=power(fac[lim],mod-2); 39 for(int i=lim;i;i--){ 40 inv[i-1]=mul(inv[i],i); 41 } 42 } 43 int c(int n,int m){ 44 return mul(fac[n],mul(inv[m],inv[n-m])); 45 } 46 int f[N],g[N]; 47 struct main{ 48 main(){ 49 scanf("%d%d",&n,&p),mod=n=10000?998244353:1e4+7; 50 first(),f[0]=g[0]=1; 51 for(int i=1;i<=n;i++){ 52 for(int j=1;j<=i;j++){ 53 if(j&1) f[i]=(f[i]+mul(power(2,mul(j,i-j)),mul(c(i,j),f[i-j])))%mod; 54 else f[i]=(f[i]-mul(power(2,mul(j,i-j)),mul(c(i,j),f[i-j]))+mod)%mod; 55 } 56 g[i]=f[i]; 57 for(int j=1;j<i;j++) g[i]=(g[i]-mul(c(i-1,j-1),mul(g[j],f[i-j]))+mod)%mod; 58 } 59 printf("%d\n",p?g[n]:f[n]); 60 exit(0); 61 } 62 }UniversalLove; 63 } 64 int main(){ 65 Moxing::main(); 66 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int ans[] = {25, 18, 543, 8939, 5503, 6794, 8693, 7469, 3864, 185198037}; 5 6 inline int gid(int n, int p) { 7 if(n == 3) return 1 + p; 8 if(n == 4) return 3; 9 if(n == 100) return 4 + p; 10 if(n == 300) return 6 + p; 11 if(n == 5000) return 8 + p; 12 return 10; 13 } 14 15 int main() { 16 static int n, p; 17 freopen("kappa.in", "r", stdin); 18 freopen("kappa.out", "w", stdout); 19 scanf("%d%d", &n, &p), printf("%d\n", ans[gid(n, p) - 1]); 20 return 0; 21 }
T3:Kappa
• 题目大意:
• 求??个点带标号的??????数目(要求联通/不要求联通)。
• 这里联通定义为:将有向边改为无向边后,所有点均在一个连通块内。
• 答案取模一个质数。
Solution:
• DP!从哪里入手呢?
• DAG图的性质?入度为0的点!
• 令????表示含??个点的??????数目(不要求联通),????表示含??个点的??????数目(要求联通)
引理:对于两个关于集合的函数??(??) 和??(??)
? 如果有:
? 那么:
? 我们记??(??, ??)表示n个点,其中只有S中的点入度为0。
? 类似定义??(??, ??)表示n个点,其中至少S中的点入度为0。
那么显然:
? 我们的目的为?? ??, ∅ 。继续推导: