\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
ABC333F
鍵
巡回しているため，無限に同じ局面になる可能性がある． しかし，確率を計算すれば収束するため，値は有限になる． 巡回部分をどの様に回避するかが鍵になる．
解法0
等比級数の公式を用いる方法． \(abs(r) < 1\) のとき， \[\begin{matrix} S &:=& a + ar + ar^{2} + \cdots \\ &=& a + rS. \end{matrix}\] よって \(S = \frac{a}{1-r}\). 上の式で，\(S\) を表すために \(S\) 自身を用いている． そこが巡回にあたる部分で，それを上手くまとめることができるのが 等比級数の和の公式．
本問ではどこで巡回しているかというと， 人数が変わらない限りループしてしまう． よって，等比級数の公式を用いて，人数が減る確率を求めておけば巡回を回避できる． そうすれば DAG になるので dp で解ける．
\(dp_{i,j} := \) 今 \(i\) 人残っていて，この \(i\)人のうち最後に \(j\) 番目の人が残る確率
とおく． \(i\) 人残っているときに，\(j\) 番目の人が消える確率を求めてけば良い．
解法1
\(dp\) の定義は解法0 と同じ． あとは，各 \(i\) に対して \(x := dp_{i,0}\) とおいて， \(dp_{i,j}\) を求める．
普通に求めようとするとサイクルになってしまう． そこで，状態(つまり頂点) \(\ (i,0)\ \) の部分でグラフを分裂させる． 頂点 \(\ (i,0)\ \) をコピーして \(\ (i,0)'\ \) とおく． \(\ (i,0)\ \)に入ってくる辺の行き先を \(\ (i,0)'\ \) に置き換える． \(\ (i,0)\ \)から出ていく辺はそのままとする． このグラフで考えれば DAG となって dp が出来る．
DP を行って，\(\ (i,0)'\ \) における値を \(x\) で表す． 実際は \(x\) の 1次式となり，\(ax + b\) の形で書ける． \(\ (i,0)'\ \) と \(\ (i,0)\ \) は，元々は同じ頂点だったので， \(dp_{(i,0)} = x\) と \(dp_{(i,0)'} = ax + b\) は一致するはずである． よって \(x = ax + b\) を得るので，これより \(x = \frac{b}{1-a}\). なお，遷移する確率が \(\frac{1}{2}\) であるから，\(a \neq 1\) を得る． これは mod \(p\) で考えても，今回は起こらない． \(p \neq 2\) のとき， \(\frac{1}{2^{m}} \equiv 1 \) mod \(p\) であることは， \(m \equiv 0\) mod \(p-1\) であることと必要十分．
注意: 解法1
実装するときは，\(dp_{(i,0)}\) の値を上書きする． += の様に書いてしまうと， \(x := dp_{(i,0)}\) に対して \(dp_{(i,0)} \leftarrow dp_{(i,j)} \) の様になってしまい， \(dp_{(i,0)'}\) に余分な \(x\) が追加されてしまう．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
//---------------------------------------------------------------------------------------------------
// periodic
struct D{
mint a,b;
D(){ // 初期化を書けば，resize したときに問題が起きない．
a = 0;
b = 0;
}
D(mint a, mint b): a(a), b(b){}
D operator += (D x){
a += x.a;
b += x.b;
return *this;
}
D operator / (mint m) const {
return D(a/m, b/m);
}
};
int main() {
ll n;
cin >> n;
rep1(i,n) dp[i].resize(i);
dp[1][0] = D(0,1);
srep(i,2,n+1){
// x := dp[i][0]
dp[i][0] = D(1,0);
rep1(j,i){
D now;
// rem: / mint(2)
if(j != i) now += dp[i-1][j-1]/mint(2);
now += dp[i][j-1]/mint(2);
// rem: periodic で [i][0] に戻ってくるので，
// そのときに上書きが正しい．間違いなのは += .
dp[i][j%i] = now;
}
mint x;
{
mint a = dp[i][0].a;
mint b = dp[i][0].b;
x = b / (mint(1)-a);
dp[i][0] = D(0,x);
}
srep(j,1,i){
mint a = dp[i][j].a;
mint b = dp[i][j].b;
dp[i][j] = D(0, a*x + b);
}
}
rep(j,n)
cout << dp[n][j].b.val() << endl;
return 0;
}
//---------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------
int main() {
ll n;
cin >> n;
mint q = mint(1)/mint(2);
dp[1][0] = 1;
srep(i,2,n+1){
r[0] = q/(mint(1)-q.pow(i));
// mint ri = r[0] / q;
rep(i,n) r[i+1] = r[i] * q;
rep1(k,i-1) dp[i][0] += r[k] * dp[i-1][(i-1-k)%i]; // rem: (i-1-k)%i : 一人消えた後なので -1
rep(j,i-1){
// dp[i][j+1] = q * (dp[i][j] + (- r[i-1] + ri )*dp[i-1][j]);
dp[i][j+1] = q*(dp[i][j] - r[i-1] *dp[i-1][j]) + r[0]*dp[i-1][j];
}
}
rep(j,n){
cout << dp[n][j].val() << endl;
}
return 0;
}
//---------------------------------------------------------------------------------------------------
