求助
查看原帖
求助
579492
CZCCZC楼主2022/7/17 17:49

RT.

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const ll MOD = 998244353LL ;
ll DP[2][134217730] , getlen[134217730] ;
ll Mx , N , i , j , k , ans , fac = 1 , nw , t , pos ;
inline ll low_bit(ll x) {
	return x & (-x) ;
}
inline ll own_pow(ll a , ll b) {
	ll res = 1 ;
	while(b) {
		if(b & 1) res = (res * a) % MOD ;
		a = (a * a) % MOD ;
		b >>= 1 ;
	}
	return res ;
}
int main() {
	cin >> N ; N -- ; DP[0][0] = 1 ; Mx = 1 << N ;
	for(nw = i = 1 ; i <= N ; nw ^= 1 , i++) {
		fill(DP[nw] , DP[nw] + (1 << i) , 0) ;
		for(j = 0 ; j < (1 << (i - 1)) ; j++) {
			DP[nw][j << 1] = (DP[nw][j << 1] + DP[nw ^ 1][j]) % MOD , pos = -1 ;
			for(k = i - 1 ; ~k ; k--) {
				t = ((j >> k) << (k + 1)) | (1 << k) | (j & ((1 << k) - 1)) ;
				if(j & (1 << k)) pos = k ;
				if(~pos) t ^= (1 << (pos + 1)) ;
				DP[nw][t] = (DP[nw][t] + DP[nw ^ 1][j]) % MOD ;
			}
		}
	}
	for(i = 1 ; i < Mx ; i++) getlen[i] = getlen[i - low_bit(i)] + 1 ;
	for(i = 0 ; i < Mx ; i++) ans = (ans + 1ll * DP[N & 1][i] * (getlen[i] + 1)) % MOD ;
	for(i = 1 ; i <= N + 1 ; i++) fac = (fac * i) % MOD ;
	ans = ans * own_pow(fac , MOD - 2) % MOD ;
	cout << ans << endl ;
	return 0 ;
}

一直显示"ld返回1"怎么回事?大佬们帮我看一下QWQ

2022/7/17 17:49
加载中...