UVA11806 Cheerleaders

roger_yrj · 2025-01-06 21:09:36 · 题解

前言

基础容斥，建议降绿

题解

根据容斥原理，答案为：保留 4 条边的方案数-保留 3 条边的方案数+保留 2 条边的方案数-保留 1 条边的方案数+保留 0 条边的方案数，组合数计算即可。

注意 1e6+7=29\times 34483。

代码

#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);
}