一道比较简单的容斥题 (?
可以容斥一下, 设 \(i, j ,k\) 分别代表 \(i\) 行有颜色, \(j\) 行有颜色, 出现 \(k\) 种颜色的方案数
\[ ans = \sum_{i=0}^n\sum_{j=0}^m\sum_{k=0}^c(-1)^{(i+j+k+n+m+c)}C_n^iC_m^jC_c^k(k+1)^{(n*m)} \]
k+1 是因为一个格子可以不填颜色, 反手一个预处理组合数, O(n^3) 稳过
代码
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #define ll long long
- using namespace std;
- const int P = 1e9+7;
- const int N = 505;
- ll C[N][N], fpw[N*N];
- int n, m, c;
- ll ans;
- int main() {
- cin>> n>> m>> c;
- fpw[0] = C[0][0] = 1;
- for (int i = 1;i <= 400; i++) {
- C[i][0] = 1;
- for (int j = 1;j <= i; j++) {
- C[i][j] = C[i-1][j] + C[i-1][j-1];
- if (C[i][j]>= P) C[i][j] -= P;
- }
- }
- int p = (n ^ m ^ c) & 1;
- for (int k = 0;k <= c; k++) {
- for (int i = 1;i <= n * m; i++) fpw[i] = fpw[i-1] * (k+1) % P;
- for (int i = 0;i <= n; i++) {
- for (int j = 0;j <= m; j++) {
- ll res = C[n][i] * C[m][j] % P * C[c][k] % P * fpw[i*j] % P;
- if (((i ^ j ^ k) & 1) ^ p) ans -= res;
- else ans += res;
- }
- }
- }
- cout << (ans % P + P) % P << endl;
- return 0;
- }
[JSOI2015] 染色问题
来源: http://www.bubuko.com/infodetail-3327490.html