[jsoi2015]染色问题
2021/8/26 23:09:47
本文主要是介绍[jsoi2015]染色问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 题意:P6076
- 思路:
容斥+dp
有三种下限要求方案数?我们来层层降维。
首先\(ans=(-1)^{c-i}*C_c^i*f[i]\)
f[i]表示至多i种颜色且满足另外两限制的方案数。
很多时候我们发现,"随便","至多","至少"要好求很多,而我们要"恰好"时就会用到容斥
\(f[i]=(-1)^{m-i}*n^{C_m^i-1}\)
这里同理降维,控制列上限,行也顺便处理掉了。 - 代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=405; ll f[N],mod=1e9+7,C[N][N]; void init() { for(int i=0;i<N;i++) C[i][0]=1; for(int i=1;i<N;i++) { for(int j=1;j<=i;j++) { C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod; } } } ll ksm(ll a,ll b) { ll mul=1; for(;b;b>>=1,a=a*a%mod) if(b&1)mul=mul*a%mod; return mul; } int main() { init(); int n,m,c; ll opt=1; scanf("%d%d%d",&n,&m,&c); for(int i=1;i<=c;i++) { opt=1; for(int j=m;j;j--) { f[i]+=opt*C[m][j]%mod*ksm(ksm(i+1,j)-1,n)%mod; f[i]%=mod,opt=mod-opt; } } ll ans=0; opt=1; for(int i=c;i;i--) ans=(ans+opt*C[c][i]%mod*f[i]%mod)%mod,opt=mod-opt; printf("%lld",ans); return 0; }
这篇关于[jsoi2015]染色问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09vue3开发前端表单缓存自定义指令,移动端h5必备插件
- 2024-05-09React Hooks在class组件中的使用方式
- 2024-03-30[OIDC in Action] 2. 基于OIDC(OpenID Connect)的SSO(纯JS客户端)
- 2024-03-29terraform jsonencode
- 2024-03-13vuex-persist
- 2024-03-11icons for vue
- 2024-03-07breadcrumbs react js
- 2024-03-06react login page example
- 2024-03-06react router uselocation
- 2024-03-04postgres jsonb_set