Cheerleaders UVA - 11806（容斥+二进制技巧）

时间：2021-12-24 02:00:00
#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define MOD 1000007

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff;

int C[][];

int main()

{

    mem(C, );

    C[][] = ;

    for(int i=; i<=; i++)

    {

        C[i][] = C[i][i] = ;

        for(int j=; j<i; j++)

            C[i][j] = ( C[i-][j-] + C[i-][j] ) % MOD;

    }

    int T, kase = ;

    int n, m, k;

    cin>> T;

    while(T--)

    {

        cin>> n >> m >> k;

        int sum = ;

        for(int i=; i< ; i++)

        {

            int r = n,c = m, b = ;

            if(i & ) r--, b++;

            if(i & ) r--, b++;

            if(i & ) c--, b++;

            if(i & ) c--, b++;

            if(b & ) sum = (sum  + MOD - C[r*c][k]) % MOD;

            else sum = (sum + C[r*c][k]) % MOD;

        }

        printf("Case %d: %d\n",++kase, sum);

    }

    return ;

}

相关文章