mayoko’s diary

プロコンとかいろいろ。

SRM 679 div1 hard: BagAndCards

解法

count[i][j] から, cnt[i][j] = (別のバッグから j というカードを取り出した時, バッグ i から あるカード k を取り出して j + k が Good な数になるような場合の数) を作ります。j+k の候補がたかだか 2*m 通りしかないので, cnt[i][j] は O(n m^2) で求められます。

これがわかれば後は簡単で, ans[i][j] は, sum(count[i][k] * cnt[j][k]) (0 <= k < m) で求められます。これは O(n^2 m) で出来ます。

const int MOD = 1e9+7;

class BagAndCards {
public:
    int getHash(int n, int m, int x, int a, int b, int c, string isGood) {
        vector<vi> count(n, vi(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                count[i][j] = x;
                x = (((ll)(x)*a+b)^c) % MOD;
            }
        }
        vi cand;
        for (int i = 0; i < 2*m-1; i++) if (isGood[i] == 'Y') cand.push_back(i);
        vector<vll> cnt(n, vll(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                for (int c : cand) {
                    if (c-j < 0 || c-j >= m) continue;
                    cnt[i][j] += count[i][c-j];
                }
                cnt[i][j] %= MOD;
            }
        }
        vector<vll> ans(n, vll(n));
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    ans[i][j] += count[i][k]*cnt[j][k] % MOD;
                }
                ans[i][j] %= MOD;
            }
        }
        ll ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) ret ^= ans[i][j];
        }
        return (int)ret;
    }
};