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; } };