Cheerleaders

?UVA - 11806?

題目傳送門

題目大意：給你三個整數n,m,k，代表有一個n行m列的場地，共有k個人，需保證在最外圍的一圈的每行每列都必須要有一個人，若這個人在對角上，則可以當做他所在的行列都已經滿足條件，問共有幾種排布方法。

解決方法：此題若是從正面算十分復雜，因此換一種思路，假設場地的四邊分別為A,B,C,D，總的情況數為C(底數n*m)(指數k)，不滿足條件的情況為有一條邊（A,B,C,D）不放人，有兩條邊不放人（AB,AC,AD,BC,BD,CD），有三條邊不放人（ABC,ABD,ACD,BCD），四條邊全不放人（ABCD），所以滿足條件的情況為總的情況數-缺一條邊+缺兩條邊-缺三條邊+缺四條邊。

AC代碼：

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <map> #include <stack> #include <queue> #include <vector> #include <bitset> #include <set> #include <utility> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; #define inf 0x3f3f3f3f #define rep(i,l,r) for(int i=l;i<=r;i++) #define lep(i,l,r) for(int i=l;i>=r;i--) #define ms(arr) memset(arr,0,sizeof(arr)) //priority_queue<int,vector<int> ,greater<int> >q; const int maxn = (int)1e5 + 5; const ll mod = 1e6+7; ll C[510][510]; void fun() {C[1][1]=1;C[1][0]=C[2][0]=C[2][2]=1;C[2][1]=2;for(int i=3;i<=500;i++){C[i][0]=C[i][i]=1;for(int j=1;j<i;j++)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;} } int main() {//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int T;fun(); /* int u,v; while(cin>>u>>v)cout<<C[u][v]<<endl;*/cin>>T;ll t1,t2,t3,t4,t5,t6,t7,t8,t9;rep(i,1,T) {ll n,m,k,a,b,c,d;cin>>n>>m>>k;t1=n*m;t2=n*(m-1);t3=(n-1)*m;t4=(n-2)*m;t5=(n-1)*(m-1);t6=n*(m-2);t7=(n-2)*(m-1);t8=(n-1)*(m-2);t9=(n-2)*(m-2);ll all=C[t1][k];a=((C[t2][k]+C[t3][k])*2)%mod;b=(C[t4][k]+C[t5][k]*4+C[t6][k])%mod;c=(C[t7][k]*2+C[t8][k]*2)%mod;d=C[t9][k];ll ans=all-a+b-c+d; /* cout<<all<<" "<<a<<" "<<b<<" "<<c<<" "<<d<<endl; */ cout<<"Case "<<i<<": ";if(k<2)cout<<0<<endl;elsecout<<(ans+mod)%mod<<endl;}return 0; }

?

總結

以上是生活随笔為你收集整理的Cheerleaders【容斥】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。