UVa 12590 - Guards II (组合数学+容斥)
2021/8/9 6:35:59
本文主要是介绍UVa 12590 - Guards II (组合数学+容斥),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4035
特别恶心的分类讨论,讨论四个角的放置方法即可
具体讨论见代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1000010; const int M = 1000000007; int T, n, m, k; int fac[maxn], ifac[maxn]; int f[105], g[10]; int qsm(int i, int po){ int res = 1; while(po){ if(po & 1) res = 1ll * res * i % M; i = 1ll * i * i % M; po >>= 1; } return res; } int C(int N, int K){ if(K < 0) return 0; if(N < K) return 0; return 1ll * fac[N] * ifac[K] % M * ifac[N-K] % M; } ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; } int main(){ fac[0] = 1; for(int i = 1 ; i <= 1000000 ; ++i) fac[i] = 1ll * fac[i-1] * i % M; ifac[1000000] = qsm(fac[1000000], M - 2); for(int i = 1000000 - 1 ; i >= 0 ; --i) ifac[i] = 1ll * ifac[i+1] * (i+1) % M; scanf("%d", &T); int kase = 0; while(T--){ int ans = 0; scanf("%d%d%d", &n, &m, &k); printf("Case %d: ", ++kase); if(n == 1 || m == 1){ printf("%d\n", C(n*m, k)); continue; } // case7 (填四个角) int ans7 = 0; ans7 = C(n*m-4, k-4); ans = (ans + ans7) % M; // case6 (只填三个角) 答案乘 4 int ans6 = 0; ans6 = C(n*m-4, k-3); ans = (ans + 2ll * ans6 % M * 2 % M) % M; // case1 (只填两个对角) 答案乘 2 int ans1 = 0; ans1 = C(n*m-4, k-2); // printf("%d\n", ans1); ans = (ans + 2ll * ans1 % M) % M; // case2 (只填第一行的两个角) 答案乘 2 int ans2 = 0; // case2.1 最后一行放 ans2 = (ans2 + ((C(n*m-4, k-2) - C((n-1)*m-2, k-2)) % M + M) % M) % M; // case2.2 最后一行不放 (容斥) memset(f, 0, sizeof(f)); for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (n-1)*(m-i)) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((n-1)*(m-i)-2, k-2) % M; } if(i & 1){ ans2 = ((ans2 - f[i]) % M + M) % M; } else{ ans2 = (ans2 + f[i]) % M; } } ans = (ans + 2ll * ans2 % M) % M; // printf("%d\n", ans2); // case3 (只填第一列的两个角) 答案乘 2 int ans3 = 0; // case3.1 最后一列放 ans3 = (ans3 + ((C(n*m-4, k-2) - C(n*(m-1)-2, k-2)) % M + M) % M) % M; // case3.2 最后一列不放 memset(f, 0, sizeof(f)); for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-i)*(m-1)) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((n-i)*(m-1)-2, k-2) % M; } if(i & 1){ ans3 = ((ans3 - f[i]) % M + M) % M; } else{ ans3 = (ans3 + f[i]) % M; } } // printf("%d\n", ans3); ans = (ans + 2ll * ans3 % M) % M; // case4 (只放一个角) 答案乘 4 int ans4 = 0; // case4.1 两排都放 ans4 = (ans4 + ((((C(n*m-4, k-1) - C((n-1)*m-2, k-1))%M - C(n*(m-1)-2, k-1))%M + C((n-1)*(m-1)-1, k-1))%M+M)%M)%M; // case4.2 只有最后一列放 int res1 = 0, res2 = 0; memset(f, 0, sizeof(f)); // 随便放满足最后一行都被占领的方案数 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (n-1)*(m-i)-1) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((n-1)*(m-i)-2, k-1) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } memset(f, 0, sizeof(f)); // 最后一列不放满足最后一行都被占领的方案数 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (n-1)*(m-1-i)) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((n-1)*(m-1-i)-1, k-1) % M; } if(i & 1){ res2 = ((res2 - f[i]) % M + M) % M; } else{ res2 = (res2 + f[i]) % M; } } ans4 = (ans4 + ((res1 - res2) % M + M) % M) % M; // case4.2 只有最后一行放 res1 = 0, res2 = 0; memset(f, 0, sizeof(f)); // 随便放满足最后一列都被占领的方案数 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (m-1)*(n-i)-1) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((m-1)*(n-i)-2, k-1) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } memset(f, 0, sizeof(f)); // 最后一行不放满足最后一列都被占领的方案数 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (m-1)*(n-1-i)) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((m-1)*(n-1-i)-1, k-1) % M; } if(i & 1){ res2 = ((res2 - f[i]) % M + M) % M; } else{ res2 = (res2 + f[i]) % M; } } ans4 = (ans4 + ((res1 - res2) % M + M) % M) % M; // printf("%d\n", ans4); ans = (ans + 2ll * ans4 % M * 2 % M) % M; // case5 (角全都不放) int ans5 = 0; // case5.1 两行两列都放 ans5 = (ans5 + (((C(n*m-4, k) - 1ll*2*C((n-1)*m-2, k)%M)%M - 1ll*2*C(n*(m-1)-2, k)%M)%M+M)%M)%M; // 随便放-至少一排不放-至少一列不放 ans5 = (ans5 + ((1ll*2*C((n-1)*(m-1)-1, k)%M*2%M + C(n*(m-2), k))%M + C((n-2)*m, k))%M)%M; // +至少一行一列不放+至少两行不放+至少两列不放 ans5 = (ans5 + ((-1ll*2*C((n-2)*(m-1), k)%M - 1ll*2*C((n-1)*(m-2), k)%M)%M+M)%M)%M; // -至少两行一列不放-至少一行两列不放 ans5 = (ans5 + C((n-2)*(m-2), k))%M; // + 至少两行两列不放 // case5.2 放两行一列 答案乘 2 int res = 0; res1 = 0; memset(f, 0, sizeof(f)); // +随便放满足最后一列都被占领的方案数 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-i)*(m-1)-2) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((m-1)*(n-i)-2, k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + res1) % M; res1 = 0; memset(f, 0, sizeof(f)); // -有一行不放满足最后一列都被占领的方案数 * 2 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-1-i)*(m-1)-1) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((n-1-i)*(m-1)-1, k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = ((res - 2ll * res1 % M) % M + M) % M; res1 = 0; memset(f, 0, sizeof(f)); // -有一列不放满足最后一列都被占领的方案数 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-i)*(m-2)) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((n-i)*(m-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = ((res - res1)% M + M) % M; res1 = 0; memset(f, 0, sizeof(f)); // +两行都不放满足最后一列都被占领的方案数 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-2-i)*(m-1)) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((n-2-i)*(m-1), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + res1) % M; res1 = 0; memset(f, 0, sizeof(f)); // +一行一列都不放满足最后一列都被占领的方案数 * 2 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-1-i)*(m-2)) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((n-1-i)*(m-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + 2ll * res1 % M) % M; res1 = 0; memset(f, 0, sizeof(f)); // -两行一列都不放满足最后一列都被占领的方案数 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-2-i)*(m-2)) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((n-2-i)*(m-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = ((res - res1) % M + M) % M; ans5 = (ans5 + 2ll * res % M) % M; // case5.3 放两列一行 答案乘 2 res = 0; res1 = 0; memset(f, 0, sizeof(f)); // +随便放满足最后一列都被占领的方案数 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (m-i)*(n-1)-2) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((n-1)*(m-i)-2, k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + res1) % M; res1 = 0; memset(f, 0, sizeof(f)); // -有一行不放满足最后一列都被占领的方案数 * 2 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (m-1-i)*(n-1)-1) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((m-1-i)*(n-1)-1, k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = ((res - 2ll * res1 % M) % M + M) % M; res1 = 0; memset(f, 0, sizeof(f)); // -有一列不放满足最后一列都被占领的方案数 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (m-i)*(n-2)) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((m-i)*(n-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = ((res - res1)% M + M) % M; res1 = 0; memset(f, 0, sizeof(f)); // +两行都不放满足最后一列都被占领的方案数 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (m-2-i)*(n-1)) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((m-2-i)*(n-1), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + res1) % M; res1 = 0; memset(f, 0, sizeof(f)); // +一行一列都不放满足最后一列都被占领的方案数 * 2 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (m-1-i)*(n-2)) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((m-1-i)*(n-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + 2ll * res1 % M) % M; res1 = 0; memset(f, 0, sizeof(f)); // -两行一列都不放满足最后一列都被占领的方案数 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (m-2-i)*(n-2)) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((m-2-i)*(n-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = ((res - res1) % M + M) % M; ans5 = (ans5 + 2ll * res % M) % M; // case5.4 放两列 res = 0; res1 = 0; memset(f, 0, sizeof(f)); // +随便放满足上下两行都被占领的方案数 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (m-i)*(n-2)) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((m-i)*(n-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + res1) % M; res1 = 0; memset(f, 0, sizeof(f)); // -一列不放满足上下两行都被占领的方案数 * 2 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (m-1-i)*(n-2)) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((m-1-i)*(n-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = ((res - 2ll*res1%M) % M + M) % M; res1 = 0; memset(f, 0, sizeof(f)); // +两列都不放满足上下两行都被占领的方案数 * 2 for(int i = 0 ; i <= m-2 ; ++i){ if(k <= (m-2-i)*(n-2)) { // 能放得下 f[i] = 1ll * C(m-2, i) * C((m-2-i)*(n-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + res1) % M; ans5 = (ans5 + res) % M; // case5.5 放两行 res = 0; res1 = 0; memset(f, 0, sizeof(f)); // +随便放满足上下两行都被占领的方案数 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-i)*(m-2)) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((n-i)*(m-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + res1) % M; res1 = 0; memset(f, 0, sizeof(f)); // -一列不放满足上下两行都被占领的方案数 * 2 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-1-i)*(m-2)) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((n-1-i)*(m-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = ((res - 2ll*res1%M) % M + M) % M; res1 = 0; memset(f, 0, sizeof(f)); // +两列都不放满足上下两行都被占领的方案数 * 2 for(int i = 0 ; i <= n-2 ; ++i){ if(k <= (n-2-i)*(m-2)) { // 能放得下 f[i] = 1ll * C(n-2, i) * C((n-2-i)*(m-2), k) % M; } if(i & 1){ res1 = ((res1 - f[i]) % M + M) % M; } else{ res1 = (res1 + f[i]) % M; } } res = (res + res1) % M; ans5 = (ans5 + res) % M; ans = (ans + ans5) % M; printf("%d\n", ans); } return 0; }
这篇关于UVa 12590 - Guards II (组合数学+容斥)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南