2024 ICPC Online 第二场（K）

#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//如果在不支持 avx2 的平台上将 avx2 换成 avx 或 SSE 之一
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
vector<int> vx;
inline void divide() {sort(vx.begin(),vx.end());vx.erase(unique(vx.begin(),vx.end()),vx.end());}
inline int mp(int x) {return upper_bound(vx.begin(),vx.end(),x)-vx.begin();}
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 210,p = 998244353,mod = p;
ll k;
ll fac[N<<1],C[N<<1][N<<1];
//参数表示的是对于第t为考虑集合a和集合b
vector<ll> fuck(int t,vector<ll> A,vector<ll> B)
{vector res(A.size()+B.size()+1,0ll);//如果t == -1的话说明所有可能的都考虑完了剩下的随意组合即可if(A.empty()||B.empty()){res[0] = 1;return res;}if(t == -1){int Asz = A.size(), Bsz = B.size();for(int i=0;i<=Asz;++i){res[i] = C[Asz][i]*C[Bsz][i]%p*fac[i]%p;}return res;}//如果a或b有一个为空那只有结果为0vector<ll> a0,a1,b0,b1;for(auto p:A) if(p>>t&1) a1.push_back(p);else a0.push_back(p);for(auto p:B) if(p>>t&1) b1.push_back(p);else b0.push_back(p);int a0sz = a0.size(), a1sz = a1.size(), b0sz = b0.size(), b1sz = b1.size();if(k>>t&1){auto tmp1 = fuck(t-1,a1,b0);auto tmp2 = fuck(t-1,a0,b1);int tmp1sz = tmp1.size(), tmp2sz = tmp2.size();for (int i=0;i<tmp1sz;++i) {for (int j=0;j<tmp2sz;++j) {res[i+j] += tmp1[i]*tmp2[j]%p, res[i+j]%=p;}}}//如果说当前位为0那么a,b当前位不同就可以直接匹配,无需往下递归//而当前位相同的需要递归求解else {//tmp1为当前位(a,b)都选0后的方案数多项式//tmp2为当前位(a,b)都选1后的方案数多项式//i表示挑选了几个a1去完成(a1,b1)配//j表示挑选了几个a0去完成(a0,b0)配//x表示挑选了几个a1去完成(a1,b0)配//y表示挑选了几个a0去完成(a0,b1)配auto tmp1 = fuck(t-1,a1,b1); // iauto tmp2 = fuck(t-1,a0,b0); // jint tmp1sz = tmp1.size(), tmp2sz = tmp2.size();for (int i=0;i<tmp1sz;++i) {for (int j=0;j<tmp2sz;++j) {for (int x = 0; x + i <= a1sz && x + j <= b0sz; ++x) {for (int y = 0; y + i <= b1sz && y + j <= a0sz; ++y) {res[i + j + x + y] += tmp1[i] * tmp2[j] % mod* C[a1sz - i][x] % mod * C[b0sz - j][x] % mod * C[b1sz - i][y] % mod * C[a0sz - j][y] % mod * fac[x] % mod * fac[y] % mod;res[i + j + x + y] %= mod;//cout<<ans[i+j+x+y]<<'\n';}}}}}return res;
}void solve()
{ll n;cin>>n>>k;vector<ll> a(n),b(n);for(int i=0;i<n;++i) cin>>a[i];for(int i=0;i<n;++i) cin>>b[i];auto ans = fuck(60,a,b);for(int i=1;i<=n;++i) cout<<ans[i]<<'\n';
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);int T = 1;//cin>>T;for (int i=0;i<N*2;i+=1) {if (i == 0) fac[i] = 1; else fac[i] = fac[i-1] * i % p;C[i][0] = 1;for (int j=1;j<=i;j+=1) C[i][j] = (C[i-1][j] + C[i-1][j-1])%p;}//cout<<fac[200]<<' '<<C[5][2]<<'\n';while(T--){solve();}
}