すごく面白かった!
スコア: 191.85 / 500.00
問題概要
"I" と "O" のみからなる文字列 が IOI 文字列であるとは、ある正の整数 が存在して
- = "I"
- = "O"
- = "I"
が成立することと定義する (1-indexed)。
いま、"I", "O", "?" のみから成る文字列 が与えられる。 の各 "?" を "I" か "O" に置き換える方法のうち、IOI 文字列となるものの個数を 1000000007 で割ったあまりを求めよ。
制約
考えたこと
面白そう!!!
現代の典型思考方法としては、まずは IOI 文字列の条件をわかりやすく言い換えること。今のままじゃ数えづらいので。また、IOI 文字列を特徴付けるよりも、補集合をとって「IOI 文字列でないための条件」を考えることにする。
まず自明な必要条件として、
- "IOI" を連続部分文字列として含んだらダメ
- "IOOOI" を連続部分文字列として含んだらダメ
- 一般に "I (奇数個の O) I" を連続部分文字列として含んだらダメ
ということが言える。よって、文字列 中の "I" の index を としたとき、この数列の連続する 2 項の差が奇数でなければならないことが言える。さらに、
- が交差が奇数の等差数列でなければならない
ということも言える。もし となるような箇所が存在すると仮定すると、
- は偶数
- の中点は "O" となる
となっているのでダメなのだ。たとえば "IOOOIOOOOOI" を想像してみるといい。これは IOI 文字列となってしまっている。
逆に、 が交差奇数の等差数列であれば、それは IOI 文字列ではない。以上で、わかりやすく特徴付けられた。
数え上げ
"?" の個数を として、"?" を埋める 通りの方法のうち、IOI 文字列とならないものを数えることにする (全体から引いたものを答える)。
- 交差 を固定
- "I" の index を表す数列 の初項 を固定
としたときに (ここまでで )、数列 の長さ が何通りあるかを考えることにする。条件は
- 文字列 の 番目より左側に "I" がない
- 文字列 の 番目と 番目の間に "I" がない
- 文字列 の 番目より右側に "I" がない
と表せる。これは予め累積和を管理することで高速に判定できる。
さて、 としてありうるものは 通りしかないことに注意すると、全体の計算量は「調和級数の和のオーダー解析」の要領で となる。十分間に合う。
コード
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; class IOIString { public: int countIOIs(vector <string> mask) { string str = ""; for (auto s: mask) str += s; int N = (int)str.size(); vector<int> inum(N+1, 0), qnum(N+1, 0); for (int i = 0; i < N; ++i) { inum[i+1] = inum[i], qnum[i+1] = qnum[i]; if (str[i] == '?') ++qnum[i+1]; else if (str[i] == 'I') ++inum[i+1]; } vector<long long> two(qnum.back()+1, 1); for (int i = 0; i < qnum.back(); ++i) two[i+1] = two[i] * 2 % MOD; // 余事象を数える long long all = two.back(), sub = 0; // I が 0 個 if (inum.back() == 0) ++sub; // I が 1 個 for (int i = 0; i < N; ++i) { if (str[i] != 'O' && inum[i] == 0 && inum.back() - inum[i+1] == 0) ++sub; } // I が 2 個以上で、交差奇数の等差数列 for (int d = 1; d <= N; d += 2) { for (int i = 0; i < N; ++i) { if (str[i] == 'O' || inum[i] > 0) continue; int prev = i+1; for (int j = i + d; j < N; j += d) { if (str[j] == 'O') break; if (inum[j] - inum[prev] > 0) break; if (inum.back() - inum[j+1] == 0) ++sub; prev = j+1; } } } long long res = (all - sub + MOD) % MOD; return res; } };