Bitwise Magic

C++(g++ 7.5.0) 解法, 执行用时: 5290ms, 内存消耗: 37364K, 提交时间: 2022-11-07 15:18:24

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using poly = vector<ll>;

constexpr ll P = 998244353;

int n,k,c;
ll fac[21], ifac[21];

ll qpow(ll a, ll k){
	ll ans = 1;
	while(k){
		if(k&1) ans = ans * a % P;
		a = a * a % P, k >>= 1;
	}
	return ans;
}

ll C(int n, int m){
	return fac[n] * ifac[m] % P * ifac[n-m] % P;
}

constexpr ll add(ll a, ll b){
	return (a+b>=P)?a+b-P:a+b;
}
constexpr ll sub(ll a, ll b){
	return (a-b< 0)?a-b+P:a-b;
}

poly& operator += (poly &A, poly B){
	assert(A.size()==B.size());
	for(int i = 0 ; i < A.size() ; i ++){
		A[i] = add(A[i], B[i]);
	}
	return A;
}

poly dot(poly A, poly &B){
	assert(A.size()==B.size());
	for(int i = 0 ; i < A.size() ; i ++){
		A[i] = A[i] * B[i] % P;
	}
	return A;
}

void fwht_xor(poly &A, bool inv){
	for(int n=A.size(), step = 1 ; step < n ; step *=2){
		for(int i = 0 ; i < n ; i += 2*step){
			for(int j = i ; j < i + step ; j ++){
				auto &u = A[j], &v = A[j+step];
				tie(u,v) = pair<ll,ll>(add(u,v), sub(u,v));
			}
		}
	}
	if(inv){
		ll invlen = qpow(A.size(), P-2);
		for(int i = 0 ; i < A.size() ; i ++) A[i] = A[i] * invlen % P;
	}
}

// dp[l, r)
vector<poly> solve(int l, int r, vector<int>a){
	if(a.empty()){
		vector<poly>ans(k+1, poly(r-l, 0));
		ans[0][0] = 1;
		return ans;
	}

	int mid = (l+r)/2;
	vector<int>lset, mset, rset;
	for(auto &val: a){
		if(val < mid) lset.push_back(val);
		else if(val < mid+k) mset.push_back(val);
		else rset.push_back(val);
	}

	auto ldp = solve(l, mid, lset);
	auto rdp = solve(mid, r, rset);

    int len = r-l;
    for(int i = 0 ; i <= k ; i ++){
    	ldp[i].resize(len,0);
    	if(rset.size()&1){
    		rdp[i].insert(rdp[i].begin(), len/2, 0);
    	}
    	else{
    		rdp[i].resize(len, 0);
    	}
    }

    vector<poly>ans(k+1, poly(len, 0));
    for(int i = 0 ; i <= k ; i ++){
    	fwht_xor(ldp[i], 0), fwht_xor(rdp[i], 0);
    }
    for(int i = 0 ; i <= k ; i ++){
    	for(int j = 0 ; j <= k-i ; j ++){
    		ans[i+j] += dot(ldp[i], rdp[j]);
    	}
    }
    for(int i = 0 ; i <= k ; i ++) fwht_xor(ans[i], 1);

    for(auto &val: mset){
    	vector<poly>tmp(k+1, poly(len, 0));
    	for(int i = 0 ; i <= k ; i ++){
    		int now = val-l-i;
    		for(int j = 0 ; j <= k-i ; j ++){
    			for(int id = 0 ; id < len ; id ++){
    				tmp[i+j][id^now] = (tmp[i+j][id^now] + ifac[i] * ans[j][id]) % P;
    			}
    		}
    	}
    	ans = tmp;
    }

    return ans;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	fac[0] = ifac[0] = 1;
	for(int i = 1 ; i <= 20 ; i ++) fac[i] = fac[i-1] * i % P;
	ifac[20] = qpow(fac[20], P-2);
    for(int i = 20 ; i >= 1 ; i --) ifac[i-1] = ifac[i] * i % P;
 
    cin >> n >> k >> c;
    vector<int>a(n);
    for(int i = 0 ; i < n ; i ++) cin >> a[i];

    ll all = fac[k] * qpow(qpow(n,k), P-2) % P;

    auto ans = solve(0, 1<<c, a);
    for(int i = 0 ; i < (1<<c) ; i ++) cout << ans[k][i] * all % P << ' ';

	return 0;
}

C++ 解法, 执行用时: 1052ms, 内存消耗: 18504K, 提交时间: 2022-04-01 12:01:11

#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<class T> 
inline void read(T &x){ 
	x=0; char c; int sign=1; 
	do{ c=getchar(); if(c=='-') sign=-1;}while(!isdigit(c)); 
	do{ x=x*10+c-'0',c=getchar();}while(isdigit(c)); 
	x*=sign; 
} 
const int N=2e6+50,mod=998244353,inv2=(mod+1)/2;
ll qpow(ll a,ll b){
	ll ret=1;
	for(;b;b>>=1,a=a*a%mod) if(b&1) ret=ret*a%mod;
	return ret;
}
void IFWT(int *a,int n){
	int m=1<<n;
	for(int k=n,len=1<<(n-1);k>=1;--k,len>>=1)
	for(int i=0;i<m;i+=1<<k)
	for(int j=i;j<i+len;++j){
		int x=a[j],y=a[j+len];
		a[j]=1LL*(x+y)%mod*inv2%mod;
		a[j+len]=1LL*(x+mod-y)%mod*inv2%mod;
	}
}
int n,k,c;
map<vector<int>,int> mp;
int F[70000],G[20][140000],H[20][70000],ans[20][70000],P[2][70];
int popcount[70000];
int fac_inv[100],inv[100];
int main(){
	fac_inv[0]=fac_inv[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=50;++i) inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=50;++i) fac_inv[i]=1LL*fac_inv[i-1]*inv[i]%mod;
	
	read(n),read(k),read(c);
	int m=1<<c,M=1<<(1+k),xor_sum=0;
	for(int i=1;i<=n;++i){
		int t;
		vector<int> temp;
		read(t);
		xor_sum^=t;
		for(int j=0;j<=k;++j) temp.push_back(t^(t-j));
		mp[temp]++;
	}
	for(int i=1;i<m;++i) popcount[i]=popcount[i>>1]^(i&1);
	
	for(int i=0;i<=k;++i)
	P[0][i]=fac_inv[i],P[1][i]=mod-fac_inv[i];
	
	for(int i=1;i<=k;++i){
		for(int j=1;j<i;++j)
		for(int t=0;t<M;++t) G[i][t]=(G[i][t]+1LL*j*G[j][t]%mod*P[(t>>(i-j))&1][i-j]%mod)%mod;	
			
		for(int t=0;t<M;++t) G[i][t]=(P[(t>>i)&1][i]+mod-1LL*inv[i]*G[i][t]%mod)%mod;
	}
	
	for(auto [vec,cnt]:mp){
		fill(F,F+m,0);
		
		for(int i=0;i<=k;++i){
			for(int t=0;t<m;++t) 
			F[t]+=popcount[t&vec[i]]<<i;
		}
		
		for(int i=0;i<=k;++i) 
		for(int j=0;j<m;++j) 
		H[i][j]=(H[i][j]+1LL*cnt*G[i][F[j]]%mod)%mod;
	}
	
	for(int t=0;t<m;++t) ans[0][t]=1;
	for(int i=1;i<=k;++i){
		for(int j=0;j<i;++j)
		for(int t=0;t<m;++t) ans[i][t]=(ans[i][t]+1LL*(j+1)*H[j+1][t]%mod*ans[i-1-j][t]%mod)%mod;
			
		for(int t=0;t<m;++t) ans[i][t]=1LL*inv[i]*ans[i][t]%mod;
	}
	IFWT(ans[k],c);
	int fac=qpow(qpow(n,k),mod-2);
	for(int i=1;i<=k;++i) fac=1LL*fac*i%mod;
	for(int i=0;i<m;++i) printf("%d ",1LL*fac*ans[k][i^xor_sum]%mod);
	return 0;
}

详情