ARC089 F : ColoringBalls(1100)
作成日：2018.01.24
最終更新日：2018.01.24
問題概要
$N$個の白いボールが一列に並んでいる。
$r$,$b$からなる長さ$K$の操作列$s$を先頭から見ていき、選んだ連続する区間(空も含む)にあるボールを$r$なら赤、$b$なら青を塗る操作を行う。
但し白いボールを青に塗ることはできない。
この時、操作が終わった後にあり得るボールの色の列の数を$10^9 + 7$で割った余りを求めよ。
制約
$1 \leq N,K \leq 70$
考え方
数えるべきものについて知るために、あるボールの色の列にすることができるかを判定することをまずは考える。
ボールの色が白、赤、青であることをそれぞれ$W$、$R$、$B$と表すとする。
実質的に操作を行わなくても良いことから、空でない区間を選んで行う操作の回数はできるだけ減らすべきである。
また区間に対する操作では区間の境目で差が生じることから、$WW$のように同じ色が連続している部分は1つのボールであるとみなしても判定結果は同じである。
特に操作が1回以上行われたかの境目は$W$と$R$,$B$の間となる。
つまり$W$をまたいだ区間に対して操作は行われていないので、ボールの列を$W$で区切ることができる。
$W$で区切られた列のうちの1つを考えると、$R$と$B$が交互に現れるものとなっている。
ここで$B$にするには$W$ではいけないという条件から、この区間を$R$にする操作がまず行われるとして良い。
すると区切られた列が$r$であればこれで終わりであり、そうでない場合はあとは$BRB...RBRB$とする塗り方を考えれば良い。
今度は操作を終わりから考える。
$r$,$b$いずれの操作でも1つの$R$,$B$を入れ替えることができ、それにより$BBB$,$RRR$が生じるから1つにまとめることができる。
以上により1回の操作で$R$と$B$を1つずつ減らすことができる。
最後に$B$が残るから1回$b$の操作を行えば良い。
以上をまとめると、$B$が$i$個ある区切られた列に対しては$(i+1)$回操作をする必要があり、1回目は$a$、2回目は$b$、3回目以降はいずれの操作でも良い、となる。
次に操作列$s$を上手く割り当てることができるかを考える。
区切られた列が$k$個あり、区切られた列にある$B$の個数をそれぞれ$t_i$とする。
$t_i$それぞれに$r$を割り当てる必要があり、$t_i > 0$となるものそれぞれに$b$を割り当てる必要がある。
そして、$t_i > 1$となるものに対してはさらに$(t_i - 1)$個の操作を割り当てる必要がある。
これらの操作はこの順で割り当てなければならないから、$s$を初めから見ていき$r$や$b$が現れたらそれぞれを必要とする列に割り当てるのが良い。
この時に割り当てる先がなければどちらの操作でも良くなった列に割り当てれば良い。
その際どこにも割り当てることができない操作ができるだけ生じないようにするためには、$t_i$が大きいものに優先して割り当てるべきである。
このようにして操作列を最後まで見終えた時に、必要な割り当てが済んだか否かで判定することができる。
判定の考察では複数の状態がまとめられたので、これを逆にたどることで数え上げをすることを考える。
まず昇順に並んだ$t_i$の列$V$を構成する。
$t_i$をボールの列に戻す時、その長さ$L$は$t_i = 0$の時は少なくとも$1$、そうでない時は少なくとも$2t_i - 1$である。
また区切られた列の間には1つ以上$W$がないといけない。
よって$t_i = a$となるものをいくつか選ぶ時に必要な情報は、$t_i$の個数と$L$の総和との和$z$から$1$引いたものである。
この時、$z-1$が$N$を超えるようなものは考えなくて良い。
$t_i$の並び替え方は$t_i = j$となるものの個数が$p_j$とすると、$\frac{(\sum{p_j})!}{\prod{p_j!}}$である。
後は必要最小限以外のボールの割り当てをすれば良い。
必要最小限のボールは$z-1$個である。
その他に$t_i > 0$の部分では両端に$R$を足すことができる。
さらに列全体の両端に$W$を足すことができる。
よって$t_i = 0$となるものが$x$個、そうでないものが$y$個あるとすると、$(N-z+1)$個のボールを$(z-1+2x+2)$箇所の色に割り当てることとなる。
これは$\frac{(N+2x+1)!}{(N-z+1)!(z+2x)!}$個ある。
$V$を定めるごとに判定問題を解くが、これは$O(K)$でできる。
確かめてみると、$V$の種類の個数がそれほど多くないのでこれで十分である。
ソースコード
マクロ等はこちら
const LL mod = 1e9 + 7;
const int MC = 202;
LL fct[MC+1];
LL invfct[MC+1];
int N,K;
string s;
vector<int> V;
LL ans;
void build(){
fct[0] = fct[1] = 1;
repp(i,2,MC+1){
fct[i] = fct[i-1] * i % mod;
}
LL x = fct[MC];
invfct[MC] = 1;
for(int i = mod - 2 ; i > 0 ; i >>= 1){
if(i % 2 == 1) (invfct[MC] *= x) %= mod;
(x *= x) %= mod;
}
repm(i,MC,0){
invfct[i-1] = invfct[i] * i % mod;
}
}
LL comb(int x , int y){
if(x < 0 || y < 0) return 0;
return invfct[x] * invfct[y] % mod * fct[x+y] % mod;
}
bool solve(int y , int z , int a , LL r , bool b){
if(z > N+1 || a > N+1) return 0;
if(b){
int x = V.size();
int itr = x - 1 , itb = x - 1;
int p = y , q = 0;
for(auto c : s){
if(c=='r'){
if(itr >= 0) --itr;
else if(p>0) --p;
else if(q) --q;
} else {
if(itb > itr){
q += V[itb]-1;
--itb;
} else if(q) --q;
}
}
if(~itr || ~itb || p || q) return 0;
LL w = fct[x+y] * r % mod;
w = w * comb(N-z+1,z+2*x) % mod;
(ans += w) %= mod;
}
solve(y,z,a+1,r,0);
V.PB(a);
for(int i = 1 ; solve(y,z+2*a*i,a+1,r*invfct[i]%mod,1) ; ++i) V.PB(a);
while(V.size() && *V.rbegin() == a) V.pop_back();
return 1;
}
int main(){
build();
cin >> N >> K;
cin >> s;
for(int i = 0 ; solve(i,i*2,1,invfct[i],1) ; ++i);
cout << ans << endl;
return 0;
}解法まとめ
$V$は要素の値が小さいものから決めていく。
$V$を決めるごとに判定問題を解き、可能であれば答えを足す。(31-59,65行)