TCO2012R3AH CowsMooing
問題概要(原文)
$N( N \leq 30)$ 個のバイナリ文字列が与えられる．それぞれを何度も繰り返して長さ $10^{100}$ ぐらいの $N$ 個の文字列にする．
ここで， $0 \leq i < 50!$ について，$N$ 個の文字列たちのうち，$i$ 文字目が $'1'$ であるような文字列の数を $A_i$ とする．
$A_i$ の分布を求めよ．数は大きくなるので $ \mathrm{mod} \, 10^{4}+7$ で求めよ．
考察
簡単な問題を考える．
長さを $2,3,5,7, \ldots, 47$ といった素数しか取らないとしよう．同じ長さのものはまとめてよい． ここで $2$ のやつの $1$ 文字目と，長さ $3$ のやつの $2$ 文字目が揃うような位置は $50!$ のうち何通りあるか考えよう． これは中国剰余定理から必ず一意に定まることが示せる． なので，文字列からいくつか取って $k$ 個になるような通り数というのを適当に数えればよい．(つまり文字列の長さとかは状態として覚えておかなくてもいい)
さて，現実には素数長でない文字列がありうる． ここで，合成数は $2,3,5,7$ のどれかを必ず含むことに着目しよう． $L = 2^4 \times 3^2 \times 5 \times 7$ とする．
与えられる文字列 $s$ について $\frac{|s|}{ \gcd(|s|,L)}$ は必ず素数(あるいは $1$ )になる． ここで $s$ を長さ $\mathrm{lcm}(L,|S|)$ になるまで繰り返す．その後長さ $L$ ごとに区切ると，長さ $L$ の文字列が $\frac{|s|}{\gcd(|s|,L)}$ 個できる．ここで，長さ $L$ の文字列の $1$ 文字目についてのみ着目する気分になると，長さ $\frac{|s|}{\gcd(|s|,L)}$ の文字列であるかのような気分になる．全ての文字列の周期が $L$ であるので，$1$ 文字目に着目しているとき，$2$ 文字目などは影響しない．
$\mathrm{dp_{1}}(i,j,k)$ を $i$ 文字目に着目しているときであって，長さ $j$ の文字列の $k$ 番目に $\text{'1'}$ がいくつあるか？としよう． また $\mathrm{dp_{2}}(i,j,k)$ を $i$ 文字目に着目しているときであって，長さ $j$ の文字列まで調べたとき，$k$ 個 $\text{'1'}$ があるような通り数，としてDPをする．
$L$ 倍だけ多く数えすぎてしまうので，$\mathrm{inv}(L)$ をかけてや る．
計算量は $O(NL \max(s_i)^{2})$ かなりヤバいがTCのサーバは早いので間に合う．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using Number = System.Int32;
public class CowsMooing
{
public int[] getDistribution(string[] patterns)
{
var n = patterns.Length;
const int MOD = 10007;
const int L = 16 * 9 * 5 * 7;
var a = new byte[L, 51, 50];
foreach (var s in patterns)
{
var l = s.Length;
var k = l / MathEx.GCD(l, L);
for (int i = 0; i < L * k; i++)
if (s[i % l] == 'M')
a[i % L, k, i / L]++;
}
var ans = new int[n + 1];
for (int i = 0; i < L; i++)
{
var dp = new int[n + 2];
dp[0] = 1;
for (int j = 1; j <= 50; j++)
{
var next = new int[n + 2];
for (int k = n; k >= 0; k--)
if (dp[k] != 0)
{
for (int l = 0; l < j; l++)
next[k + a[i, j, l]] = (next[k + a[i, j, l]] + dp[k]) % MOD;
}
dp = next;
}
for (int k = 0; k <= n; k++)
ans[k] = (ans[k] + dp[k]) % MOD;
}
var inv = (int)BigInteger.ModPow(L, MOD - 2, MOD);
for (int i = 0; i <= n; i++)
ans[i] = (ans[i] * inv) % MOD;
return ans;
}
}
#region gcd,lcm
static public partial class MathEx
{
static public Number GCD(Number n, Number m)
{
bool f = true;
for (; n != 0 && m != 0; f ^= true)
{
if (f)
m %= n;
else n %= m;
}
return n == 0 ? m : n;
}
}
#endregion
コメント
- sigmaさんの実装をかなり参考にした
- 中国剰余定理をうまく使って状態をバラしたりまとめたりするのが本質
- こういう系は本当に苦手…
