## 2016年1月15日 星期五

### [UVa 12590]Guards II

(Bottom is the English version)

Cover0(N,M,K)：N*M長方形中放K個守衛使得第1行到第M行都有守衛，符合條件的情況數量
Cover1(N,M,K)：和Cover0一樣，只是左上角那個點不能放守衛
Cover2(N,M,K)：和Cover1一樣，只是連右上角也不能放守衛(所以左上角和右上角都不能放)

(English version)

The key point is inclusion-exclusion principle.

Because of the particularity of corner cells (if you place a guard here, he can cover two lines of border) and there are only four such cell, we can enumerate the allocation of corner guards, and then discuss, at what circumstances all border cells can be covered.
Definitions:
Cover0(N,M,K)：place K guards in N*M grid, such that each column from 1-st to M-th has at least one guard. The return value is the number of circumstances that meet the restrictions above.
Cover1(N,M,K)：Same as Cover0, but you can't place a guard at the up-left cell.
Cover2(N,M,K)：Same as Cover1, but you can't place a guard at the up-right cell(So you can place guard in neither up-left cell nor up-right cell).
Time complexities of functions above shouldn't exceed O(max(N,M)).

Case 1：All four corners are empty

First, we can calculate the number of circumstances, such that each of four lines of border has at least one guard, here I use inclusion-exclusion principle.
If there exist a line of border that has no guard, suppose it's down border.
There are still some exceptions that down border can be fully covered.
That is, each column has at least one guard exists.
So the down border is fully covered with human wave tactics.
The number of such exceptions is Cover2(N,M,K).
Notice that this will have duplicates with the exceptions of no guard on the up border, so after adding them together, we must deduct such duplicates.
The number of such duplicates is Cover0(N,M,K).
For another direction, just swap N and M, and handle it the same way.

Case 2: Only one corner has guard

For convenience, we only consider the guard to be placed at up-left corner.
Same as above, we can use inclusion-exclusion principle to get the number of circumstances, such that both down border and right border has at least one guard.
Also, there are exceptions that allow a empty down border.
That is, each column from 2-nd to M-th has at least one guard(Because column 1 already has a guard on the corner).
The number of such exceptions is Cover2(N,M,K)+Cover1(N,M,K).
For another direction, just swap N and M.

Case 3: Two of the adjacent corners has guard

For convenience, we only consider the guard to be placed at up-left corner and up-right corner.
The same, we can use inclusion-exclusion principle to get the number of circumstances, such that down border has at least one guard.
Again, there are exceptions that allow a empty down border.
That is, each column from 2-nd to (M-1)-th has at least one guard.
The number of such exceptions is Cover2(N,M,K)+2*Cover1(N,M,K)+Cover0(N,M,K).
For another direction, just swap N and M.

Case 4: Two of the opposite corners has guard

All border cells are covered even if you haven't placed any on it.
Place guards as you like, the number of circumstances is C(N*M-4,K-2)(Four corners has been decided in advance and need to be excluded, and we've already used two guards).

Case 5: Three of the corners has guard

All border cells are covered even if you haven't placed any on it.
Place guards as you like, the number of circumstances is C(N*M-4,K-3)(Four corners has been decided in advance and need to be excluded, and we've already used three guards).

Case 6: All of the four corners has guard
I don't want to say that again. XD

Cover0, Cover1, Cover2, and C might be calculated many times, so it's recommend to use memorized search to improve performance.

Weight the six numbers above and then plus them together, this should be the answer

Don't forget to module 1000000007 at any time for fear of overflowing~

Time complexity: O(N*M*max(N,M)*K)

code:
```#include<cstdio>
#include<algorithm>
#include<cassert>
using namespace std;
typedef long long LL;
const LL MOD=1000000007LL;
LL C_DP;
LL C(const int a,const int b)
{
assert(a>=0);
if(b<0||a<b)return 0LL;
LL &ans=C_DP[a][b];
if(ans!=-1LL)return ans;
if(b==0LL||b==a)return ans=1LL;
ans=(C(a-1,b-1)+C(a-1,b))%MOD;
//    printf("C(%d,%d)=%lld\n",a,b,ans);
return ans;
}
LL Cover0_DP;
LL Cover0(const int N,const int M,const int K)
{
if(K<0)return 0LL;
LL &ans=Cover0_DP[N][M][K];
if(ans!=-1LL)return ans;
ans=0LL;
for(int blank=0;blank<=M;blank++)
{
const LL v=(C(M,blank)*C((M-blank)*N,K))%MOD;
if(blank%2==0)ans+=v;
else ans-=v;
}
//    printf("Cover0(%d,%d,%d)=%lld\n",N,M,K,ans);
return ans=(ans%MOD+MOD)%MOD;
}
LL Cover1_DP;
LL Cover1(const int N,const int M,const int K)
{
if(K<0)return 0LL;
LL &ans=Cover1_DP[N][M][K];
if(ans!=-1LL)return ans;
ans=Cover0(N,M,K);
for(int cnt=1;cnt<=N;cnt++)ans-=C(N-1,cnt-1)*Cover0(N,M-1,K-cnt)%MOD;
//    printf("Cover1(%d,%d,%d)=%lld\n",N,M,K,ans);
return ans=(ans%MOD+MOD)%MOD;
}
LL Cover2_DP;
LL Cover2(const int N,const int M,const int K)
{
if(K<0)return 0LL;
LL &ans=Cover2_DP[N][M][K];
if(ans!=-1LL)return ans;
ans=Cover1(N,M,K);
for(int cnt=1;cnt<=N;cnt++)ans-=C(N-1,cnt-1)*Cover1(N,M-1,K-cnt)%MOD;
//    printf("Cover2(%d,%d,%d)=%lld\n",N,M,K,ans);
return ans=(ans%MOD+MOD)%MOD;
}
LL Solve0(const int N,const int M,const int K)
{
LL a=C(N+M+N+M+N*M,K);
a-=2LL*C(N+M+N+N*M,K);
a-=2LL*C(M+N+M+N*M,K);
a+=4LL*C(N+M+N*M,K);
a+=1LL*C(N+N+N*M,K);
a+=1LL*C(M+M+N*M,K);
a-=2LL*C(N+N*M,K);
a-=2LL*C(M+N*M,K);
a+=1LL*C(N*M,K);
//    printf("a=%lld,(%lld,%lld)\n",a,Cover2(N+1,M+2,K),Cover0(N,M+2,K));
a+=2LL*Cover2(N+1,M+2,K)-Cover0(N,M+2,K);
//    printf("a=%lld\n",a);
a+=2LL*Cover2(M+1,N+2,K)-Cover0(M,N+2,K);
//    printf("a=%lld\n",a);
return (a%MOD+MOD)%MOD;
}
LL Solve1(const int N,const int M,const int K)
{
LL a=C(N+M+N+M+N*M,K);
a-=C(N+M+N+N*M,K);
a-=C(M+N+M+N*M,K);
a+=C(N+M+N*M,K);
a+=Cover2(N+1,M+2,K)+Cover1(N+1,M+1,K);
a+=Cover2(M+1,N+2,K)+Cover1(M+1,N+1,K);
return (a%MOD+MOD)%MOD;
}
LL Solve2(const int N,const int M,const int K)
{
LL a=C(N+M+N+M+N*M,K);
a-=C(N+M+N+N*M,K);
a+=Cover2(N+1,M+2,K)+2LL*Cover1(N+1,M+1,K)+Cover0(N+1,M,K);
return (a%MOD+MOD)%MOD;
}
int N,M,K;
LL Solve()
{
if(N>M)swap(N,M);
if(N==1)return C(N*M,K);
N-=2,M-=2;
LL ans=Solve0(N,M,K);
//    printf("ans=%lld\n",ans);
(ans+=4LL*Solve1(N,M,K-1))%=MOD;
//    printf("ans=%lld\n",ans);
(ans+=2LL*Solve2(N,M,K-2))%=MOD;
//    printf("ans=%lld\n",ans);
(ans+=2LL*Solve2(M,N,K-2))%=MOD;
//    printf("ans=%lld\n",ans);
(ans+=2LL*C(N+M+N+M+N*M,K-2))%=MOD;
//    printf("ans=%lld\n",ans);
(ans+=4LL*C(N+M+N+M+N*M,K-3))%=MOD;
//    printf("ans=%lld\n",ans);
(ans+=1LL*C(N+M+N+M+N*M,K-4))%=MOD;
//    printf("ans=%lld\n",ans);
return (ans%MOD+MOD)%MOD;
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
for(int i=0;i<=10000;i++)for(int j=0;j<=100;j++)C_DP[i][j]=-1LL;
for(int i=0;i<=100;i++)for(int j=0;j<=100;j++)for(int k=0;k<=100;k++)Cover0_DP[i][j][k]=Cover1_DP[i][j][k]=Cover2_DP[i][j][k]=-1LL;
int testcase;scanf("%d",&testcase);
while(testcase--)
{
scanf("%d%d%d",&N,&M,&K);
static int kase=1;
printf("Case %d: %lld\n",kase++,Solve());
}
return 0;
}```