SRM 452 div1 med: IOIString
IOI
解法
IOIString でない string の数を数えることにします。
まず, 全部 O で構成されているような string は IOIString ではないです。
また, I がひとつだけ存在する string も IOIString ではないです。
I が2つある string は, I の登場する座標が x, y であったとすると, x と y の偶奇が一致しない場合のみ, IOIString ではないです。
I が 3 つある string は, I の登場する座標が x, y, z であったとすると, x と y, x と z, y と z の座標が一致しないことがまず第一条件です。ただ, こうすると x と z の偶奇は一致しています。しかし, y = (x+z)/2 であったとすると, IOI は構成されないので, y = (x+z)/2 も満たせば IOIString ではないです。
I が 4 つ以上ある場合も同じように, x[0], x[1], ..., x[m] が偶奇交互, x[i] = (x[i-1]+x[i+1])/2 となれば良いです。
このような non-IOIString は O(N^2 log N) で数え上げることが出来ます。
I が始まる位置 start と, I の感覚 d(これは奇数) を決めて, start 〜 start+n*d が入力からありえるなら non-IOIString の数が 1 増える, というのを正直に回すと, start と d の決め方で O(N^2), start 〜 start+n*d の n の候補が 1/1 + 1/2 + ... + 1/n となるので O(log N) で計算できます。
文字列中の I の数に注目する感じで「入力から考えている文字列がありえるか」を考えています。詳しいことはコード参照。
const int MOD = 1e9+7; class IOIString { public: int countIOIs(vector <string> mask) { string s; for (string t : mask) s += t; int n = s.size(); if (n <= 2) return 0; int ans = 1, icnt = 0; for (int i = 0; i < n; i++) { if (s[i] == '?') (ans *= 2) %= MOD; else if (s[i] == 'I') icnt++; } int minus = 0; for (int d = 1; d < n; d+=2) { for (int start = 0; start < n; start++) { int cnt = 0; for (int j = 0; start+j*d < n; j++) { if (s[start+j*d] == 'I') cnt++; else if (s[start+j*d] == 'O') break; if (cnt == icnt) { if (d != 1 && j == 0) continue; minus++; } } } } cout << minus << endl; if (!icnt) minus++; cout << minus << endl; ans = (ans-minus+MOD)%MOD; return ans; } };