首页 > 代码库 > bzoj 4487: [Jsoi2015]染色问题
bzoj 4487: [Jsoi2015]染色问题
先贴一个题解吧,最近懒得要死2333,可能是太弱的原因吧,总是扒题解,(甚至连题解都看不懂了),blog也没更新,GG
http://blog.csdn.net/werkeytom_ftd/article/details/52527740
容斥原理真的很神奇233
1 #include <bits/stdc++.h> 2 #define LL long long 3 using namespace std; 4 5 const int maxn=500; 6 const int mod=1e9+7; 7 8 int fac[maxn],inv[maxn]; 9 void pre() 10 { 11 fac[0]=1; for (int i=1; i<=400; i++) fac[i]=(LL)fac[i-1]*i%mod; 12 inv[0]=inv[1]=1; 13 for (int i=2; i<=400; i++) inv[i]=(LL)(mod-mod/i)*inv[mod%i]%mod; 14 for (int i=2; i<=400; i++) inv[i]=(LL)inv[i]*inv[i-1]%mod; 15 } 16 int ksm(int x, int p) 17 { 18 int sum=1; 19 for (;p;p>>=1,x=(LL)x*x%mod) 20 if (p&1) sum=(LL)sum*x%mod; 21 return sum; 22 } 23 int C(int n, int m) 24 { 25 return (LL)fac[n]*inv[m]%mod*inv[n-m]%mod; 26 } 27 28 int n,m,p,ans; 29 int main() 30 { 31 cin>>n>>m>>p; pre(); 32 for (int i=0; i<=n; i++) 33 for (int k=0; k<=p; k++) 34 { 35 int qwq=(LL)C(n,i)*C(p,k)%mod; 36 int orz=ksm((1-ksm(k+1,i)+mod)%mod,m); 37 qwq=(LL)qwq*orz%mod; 38 if ((n+m+p-i-k)&1) qwq=-qwq; 39 ans=(ans+qwq)%mod; 40 } 41 printf("%d\n",(ans+mod)%mod); 42 return 0; 43 }
bzoj 4487: [Jsoi2015]染色问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。