EZOJ #82

传送门

分析

首先我们发现$k$位数实际就是一位的情况的$k$次方

考虑一开始的总方案数是$2^{nm}$

我们每一次枚举其中有$i$行$j$列

对于这种情况的容斥系数为$(-1)^{i+j}$

方案数为$C_n^i*C_m^j*2^{(n-i)(m-j)}$

表示$n$行选$i$行，$m$列选$j$列，除此以外的点随便填有多少种方案

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

const long long mod = 1e9+;

long long c[][],n,m,k;

inline void getc(){

    int i,j;

    c[][]=;

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

      c[i][]=c[i][i]=;

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

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

        c[i][j]=(c[i-][j]+c[i-][j-])%mod;

    return;

}

inline long long pw(long long x,long long p){

    long long res=;

    x%=mod;

    while(p){

      if(p&)res=res*x%mod;

      x=x*x%mod;

      p>>=;

    }

    return res;

}

int main(){

    long long i,j,t;

    scanf("%lld",&t);

    getc();

    while(t--){

      scanf("%lld%lld%lld",&n,&m,&k);

      long long Ans=pw(,n*m);

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

        for(j=;j<=m;j++){

          if(i==&&j==)continue;

          if((i+j)%){

              Ans=(Ans+mod-c[n][i]*c[m][j]%mod*pw(,(n-i)*(m-j))%mod)%mod;

          }else {

              Ans=(Ans+c[n][i]*c[m][j]%mod*pw(,(n-i)*(m-j))%mod)%mod;

          }

        }

      printf("%lld\n",pw(Ans,k));

    }

    return ;

}

巴特西

EZOJ #82

最新文章

热门文章