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

コメント

  • 条件を満たさないものを数える系ニガテ