专栏文章

UVA11806 Cheerleaders

rroger_yrj
UVA11806题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqkqmmg
此快照首次捕获于
2025/12/04 06:24
3 个月前
此快照最后确认于
2025/12/04 06:24
3 个月前
查看原文

前言

基础容斥，建议降绿

题解

根据容斥原理，答案为：保留 44 条边的方案数-保留 33 条边的方案数+保留 22 条边的方案数-保留 11 条边的方案数+保留 00 条边的方案数，组合数计算即可。
注意 1e6+7=29×344831e6+7=29\times 34483。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int mod=1e6+7,N=510;
int n,m,k,C[N][N];
void solve(int T){
	cin>>n>>m>>k;
	cout<<"Case "<<T<<": "<<(C[n*m][k]-C[n*m-n][k]+mod-C[n*m-n][k]+mod-C[n*m-m][k]+mod-C[n*m-m][k]+mod
							+C[n*m-n-m+1][k]+C[n*m-n-m+1][k]+C[n*m-n-m+1][k]+C[n*m-n-m+1][k]+C[n*m-n-n][k]+C[n*m-m-m][k]
							-C[n*m-n-n-m+2][k]+mod-C[n*m-n-n-m+2][k]+mod-C[n*m-n-m-m+2][k]+mod-C[n*m-n-m-m+2][k]+mod+C[n*m-n-n-m-m+4][k])%mod<<"\n";
}
int main(){
	int T;cin>>T;
	C[0][0]=1;
	for(int i=1;i<=500;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++){
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
		}
	}
	for(int i=1;i<=T;i++)solve(i);
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...