[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一樣，只是連右上角也不能放守衛(所以左上角和右上角都不能放)
以上的函數計算時間必須在O(max(N,M))以內

情況一：四個角落都沒有守衛
我們可以先計算四條邊界都至少有一位守衛的情況數量，這裡我使用排容原理
如果有一條邊界完全沒有守衛，假設是下邊界好了，有一些例外狀況是合法的：上面從左到右的每一行都至少有一個守衛
所以就用人海戰術把下邊界完全覆蓋起來了
這種例外狀況的數量是Cover2(N,M,K)
注意，和上邊界沒守衛的例外狀況會有重複的情況，因此相加之後要扣掉
重複情況的數量是Cover0(N,M,K)
另一個方向N、M互換就好

情況二：只有其中一個角落有守衛
為了方便說明，我們只討論守衛放在左上角的情況
一樣，我們可以先用排容原理計算右邊界和下邊界都至少有一位守衛的情況數量
然後也有一些例外狀況允許下邊界完全沒有守衛：上面從第2行到第M行都至少有一個守衛(因為第1行已經有角落的守衛了)
這種例外狀況的數量是Cover2(N,M,K)+Cover1(N,M,K)
另一個方向N、M互換就好

情況三：其中兩個相鄰的角落有守衛
為了方便說明，我們只討論守衛放在左上角和右上角的情況
一樣，我們可以先用排容原理計算下邊界至少有一位守衛的情況數量

也有一些例外狀況允許下邊界完全沒有守衛：上面從第2行到第M-1行都至少有一個守衛
這種例外狀況的數量是Cover2(N,M,K)+2*Cover1(N,M,K)+Cover0(N,M,K)
另一個方向N、M互換就好

情況四：其中兩個相對的角落有守衛
就算沒多放守衛也已經覆蓋所有邊界格子了
隨便亂放，數量為C(N*M-4,K-2)(四個角落已經決定好了要扣掉，而且已經用掉了兩個守衛)

情況五：其中三個角落有守衛
就算沒多放守衛也已經覆蓋所有邊界格子了
隨便亂放，數量為C(N*M-4,K-3)(四個角落已經決定好了要扣掉，而且已經用掉了三個守衛)

情況六：四個角落都有守衛
不想講了XD

注意到，上述的Cover0、Cover1、Cover2和C在計算過程中會被使用很多次，使用記憶化搜索可以大幅提升效率

上面的六個數字加權後加起來，就是答案了
別忘了隨時模1000000007以免爆long long

時間複雜度O(N*M*max(N,M)*K)

(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

Please be noted that 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[10001][101];
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[101][101][101];
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[101][101][101];
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[101][101][101];
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;
}