問題
解法
上の行から決めていきます。
i 行目のマスを全て決めた時、l_j >= i となる j がなるべく多くなるように k, l を決めておいて損しません。
いま、i - 1 行目までのマスを決めたときの l_j >= i - 1 とできる j の集合が S であるとします。
l_j >= i とできる j の集合が T となるような i 行目のマスの決め方が何通りあるかを考えます。
これは簡単な式になって、
T が S の部分集合でない時は 0 通りで、
部分集合の時は、W + 1 - (|S| - |T|) となります。
k_i は基本的には 0 以上 W 以下の全ての値を取れますが、k_i = x かつ x は S に含まれるかつ x は T に含まれない、とすることは不可能(その場合は k_i = x - 1 として x を T に含めていいため)であることからこの式が出てきます。
dpしたくなって、適当な係数をかければ集合のサイズでまとめて良いことから、l_j < i となった要素の個数に注目して書くと、
mint ans=0;
for(int t=1;t<=H;t++){
vector<mint> ne(W+1);
for(int j=0;j<=W;j++){
for(int a=0;a+j<=W;a++){
ne[a+j]+=pa[j]*comb(a+j,a)*(W+1-a);
}
}
pa=ne;
}
for(int j=0;j<=W;j++){
ans+=pa[j]*comb(W,j);
}
cout<<ans.val()<<endl;
このような3乗解にできます。
グッと睨むと結局多項係数になってるじゃん、ということでその部分をバラすと、
{ (W+1-i) / i! * x^i } ^ H * (1 / i! * x^i) の x^W の係数 * W! が答えになります。
これは結局 (W+1-x)^H * exp((H+1)*x) になるので、
(W+1-x)^H = comb(H,j) * (W+1)^j * (-x)^(H-j) の 0<=j<=H についてのsum
を利用することでO(H+W)で解くことができました。
提出
https://atcoder.jp/contests/agc035/submissions/39384404
感想
まさか自分が詰めをFPSでできるなんて！？と感動していたりする
最初は式変形が下手くそすぎてpowにしかならずに窃盗して通して、そのあともう一度考え直した、使いこなすのはまだ遠い
