CS Academy #57 - Binary Flips

問題

CS Academy

問題概要

のバイナリ行列がある。はじめ、行列の全要素は0である。この行列に対して、以下の操作を回行う：

• 行列のセル()を1つ指定し、行目の全要素をバイナリ反転し、列目の全要素を全要素をバイナリ反転する(よって、セルは2回反転されるので変化しないことになる)。

操作を回行った後に、値がになっているセルの個数が個になるような操作の方法は何通りあるか、で割った余りを答えよ。

• テストケース数
• 
• 

アイデア

行に注目して、行目に対して操作を行った回数の偶奇の値を、列に注目して、列目に対して操作を行った回数の偶奇の値をと表すことにすると、となるにはとなることが条件になると言える。

まず、とを独立にして考えてみる。

数列 (サイズ = )に関して、dp[i][j] = i回操作を行った時に、1の個数がj個になるような操作の個数というものを考える。まず、初期値はdp[0][0] = 1で与えられる。

次に操作を起こる行に注目すると、0なら、1が1つ増えるので、0の個数を考慮するとdp[i+1][j+1] += dp[i][j]*(N-j)と配ることが出来る。逆に1の部分に対して操作をするならdp[i+1][j-1] += dp[i][j]*jと配ることが出来る。

とに対して、このdp配列の前計算はそれぞれとで行うことが出来る(それぞれの配列の名前をdr,dcとしておく)。

この前計算が終わってしまえば、あとは1になる行の個数と列の個数を全探索する()。それぞれ行、列あるとすると1になるセルの個数は、(どちらかが0でもう片方が1であれば良いので)個となる。これがに一致する時のdr[k][r1] * dc[k][c1]を足し上げていけば良いことになる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))

const ll mod = 1e9+7;

vector<ll> make_table(int n, int k)
{
    vector<ll> dp(n+1);
    dp[0] = 1;
    rep(i,k)
    {
        vector<ll> nx(n+1);
        rep(j,n+1)
        {
            if(j+1<=n) (nx[j+1]+=dp[j]*(n-j))%=mod;
            if(j-1>=0) (nx[j-1]+=dp[j]*j)%=mod;
        }
        dp = nx;
    }
    return dp;
}

ll solve(int n, int m, int k, int s)
{
    vector<ll> dr = make_table(n,k), dc = make_table(m,k);
    ll ans = 0;
    rep(r1,n+1)rep(c1,m+1)
    {
        if(r1*(m-c1) + c1*(n-r1) == s) (ans += dr[r1]*dc[c1])%=mod;
    }
    return ans;
}

int main()
{
    int T;
    cin >>T;
    while(T--)
    {
        int n,m,k,s;
        cin >>n >>m >>k >>s;
        cout << solve(n,m,k,s) << endl;
    }
    return 0;
}