SRM452D1M IOIString
典型数え上げといえばそうなのかもしれない？
問題概要(原文)
$N$ 文字の文字列 $S$ が与えられる．これは 'I','O', '?' のどれかからなり，'?' は 'I' か 'O' になる．
$S_{a} = S_{a+2b} = \text{'I'},S_{a+b} = \text{'O'}$ となるような $(a,b)$ が存在するならば， $S$ はいい文字列である．
'?' に 'I' か 'O' を埋めたとき，いい文字列になるようなものは何通りあるか？
考察
いい文字列を数えるのは難しいので，いい文字列でないもの(以下悪い文字列と呼ぶ)を数える． どのようなものが悪い文字列であるという条件を満たすか？
'O'のみからなる文字列は自明に悪い文字列である． 'I'が $1$ つしか含まれない文字列も悪い文字列である．
では'I'が $k$ 個含まれる悪い文字列があっととき，これに任意個の 'O' を追加したあと，どれか $1$ つを 'I' に置換してできる文字列が悪い文字列となる条件はなんだろうか？
- $k = 1$ のとき，直前の'I'との距離が奇数 $n$ ならば，悪い文字列になる
- $k = 2$ のとき，直前の'I'との距離が奇数 $n$ であって， $2$ つ前の'I' との距離が $2n$ であるときのみ悪い文字列になる
- 一般の $k$ について，'I'同士の感覚がある奇数 $n$ ならば悪い文字列になる
このような簡単なものになった．'I' の始点と，'I'同士の距離 $n$ を全探索しよう． 全探索するとき，変な位置に'I'がないかを調べるのと，これ以降に'I'がないかを調べればよい．
計算量は $O(N^2 logN)$
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class IOIString
{
public int countIOIs(string[] mask)
{
var s = mask.SelectMany(x => x).ToArray();
var n = s.Length;
var all = ModInteger.Pow(2, s.Count(x => x == '?'));
for (int i = 0; i < n; i++)
for (int j = 1; j <= n; j++)
{
if (i + 2 * j >= n) break;
if (s[i] == 'I' && s[i + j] == 'O' && s[i + 2 * j] == 'I') return (int)all.num;
}
if (s.Count(x => x == 'I') == 0) all -= 1;
var one = new int[n + 1];
for (int i = 0; i < n; i++)
{
one[i + 1] += one[i];
if (s[i] == 'I') one[i + 1]++;
}
for (int a = 0; a < n; a++)
{
if (s[a] == 'O') continue;
if (one[n] - one[a + 1] == 0) all -= 1;
for (int b = 1; b <= n; b += 2)
{
if (a + b >= n) break;
var cnt = one[n] - one[a];
for (var ptr = a; ptr < n; ptr += b)
if (s[ptr] == 'I') cnt--;
if (cnt != 0) continue;
for (var ptr = a + b; ptr < n; ptr += b)
{
if (s[ptr] == 'O') break;
if (one[n] - one[ptr + 1] == 0)
all -= 1;
}
}
if (s[a] == 'I') break;
}
return (int)all.num;
}
}
#region ModNumber
public partial struct ModInteger
{
public const long Mod = (long)1e9 + 7;
public long num;
public ModInteger(long n) : this() { num = n % Mod; if (num < 0) num += Mod; }
public override string ToString() { return num.ToString(); }
public static ModInteger operator +(ModInteger l, ModInteger r) { var n = l.num + r.num; if (n >= Mod) n -= Mod; return new ModInteger() { num = n }; }
public static ModInteger operator -(ModInteger l, ModInteger r) { var n = l.num + Mod - r.num; if (n >= Mod) n -= Mod; return new ModInteger() { num = n }; }
public static ModInteger operator *(ModInteger l, ModInteger r) { return new ModInteger(l.num * r.num); }
public static ModInteger operator ^(ModInteger l, long r) { return ModInteger.Pow(l, r); }
public static implicit operator ModInteger(long n) { return new ModInteger() { num = n }; }
public static ModInteger Pow(ModInteger v, long k)
{
ModInteger ret = 1;
var n = k;
for (; n > 0; n >>= 1, v *= v)
{
if ((n & 1) == 1)
ret = ret * v;
}
return ret;
}
}
#endregion
コメント
- 条件を満たさないものを数える系ニガテ
