好神啊 ~
打表程序：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 140000000
#define ll long long
#define mod 998244353
#define setIO(s) freopen(s".in","r",stdin) , freopen(s".out","w",stdout)
using namespace std;
int f[2][N];
int cnt[N];
ll qpow(ll x,ll y) {
ll ans=1;
while(y) {
if(y&1) {
ans=ans*x%mod;
}
x=x*x%mod;
y>>=1;
}
return ans;
}
int main() {
// setIO("input");
for(int n=1;n<=30;n+=2) {
int i,j,k,d,t,pos;
ll ans=0,fac=1;
--n;
f[0][0]=1;
for(d=i=1;i<=n;++i,d^=1) {
memset(f[d],0,sizeof(int)*(1<<i));
for(j=0;j<(1<<(i-1));++j) {
f[d][j<<1]=(f[d][j<<1]+f[d^1][j])%mod,pos=-1;
for(k=i-1;k>=0;--k) {
t=((j>>k)<<(k+1))|(1<<k)|(j&((1<<k)-1));
if(j&(1<<k)) pos=k; // 这里有一
if(pos>=0) t^=(1<<(pos+1));
f[d][t]=(f[d][t]+f[d^1][j])%mod;
}
}
}
for(i=1;i<(1<<n);++i) {
cnt[i]=cnt[i-(i&-i)]+1;
}
for(i=0;i<(1<<n);++i) {
ans=(ans+1ll*f[n&1][i]*(cnt[i]+1))%mod;
}
for(i=1;i<=n+1;++i) {
fac=fac*i%mod;
}
printf("%lld\n",ans*qpow(fac,mod-2)%mod);
}
return 0;
}
表：
#include <cstdio>
int ans[40]={
1,
499122178,
2,
915057326,
540715694,
946945688,
422867403,
451091574,
317868537,
200489273,
976705134,
705376344,
662845575,
331522185,
228644314,
262819964,
686801362,
495111839,
947040129,
414835038,
696340671,
749077581,
301075008,
314644758,
102117126,
819818153,
273498600,
267588741,
};
int main() {
int n;
scanf("%d",&n);
printf("%d\n",ans[n-1]);
return 0;
}