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

?