设\(f_{i,j}\)表示在有i个人的队列中，第j个人成为第一个的概率。
\(f_{n,1}=\frac{1}{2}f_{n,n}\)
\(f_{n,2}=\frac{1}{2}f_{n-1,1}+\frac{1}{2}f_{n,1}\)
...
\(f_{n,n}=\frac{1}{2}f_{n-1,n-1}+\frac{1}{2}f_{n-1,n-1}\)
先解出\(f_{n,n}\)再回代即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define A puts("Yes")
#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e6+5;
const ll inf = 1ll << 60;
const ll mo = 998244353;
const ll mo1=1e9+7;
const ll mo2=1e9+9;
const ll P=131;
const ll Q=13331;
ll f[3005][3005],n,inv2,inv[N],b[N];
void add(ll &x,ll y){
x=(x+y)%mo;
}
ll power(ll a,ll b){
ll t=1,y=a%mo;
while (b) {
if (b&1) t=t*y%mo;
y=y*y%mo;
b/=2;
}
return t;
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%lld",&n);
inv2=-(mo/2);
inv2+=mo;
b[0]=1;
fo(i,1,n) b[i]=b[i-1]*2ll%mo;
inv[0]=1;
fo(i,1,n) inv[i]=inv[i-1]*inv2%mo;
f[1][1]=1;
ll t=0;
fo(i,2,n) {
t=0;
fo(j,1,i-1) {
add(t, inv[j]*f[i-1][i-j]%mo);
}
f[i][i]=t*b[i]%mo*power(b[i]-1, mo-2)%mo;
f[i][1]=inv2*f[i][i]%mo;
fo(j,2,i-1) f[i][j]=(f[i-1][j-1]+f[i][j-1])%mo*inv2%mo;
}
fo(i,1,n) {
f[n][i]=(f[n][i]%mo+mo)%mo;
printf("%lld ",f[n][i]);
}
return 0;
}