結果

問題 No.2237 Xor Sum Hoge
コンテスト
ユーザー no way
提出日時 2023-03-03 22:37:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,861 ms / 10,000 ms
コード長 2,563 bytes
コンパイル時間 1,566 ms
コンパイル使用メモリ 177,848 KB
実行使用メモリ 9,860 KB
最終ジャッジ日時 2024-09-17 23:38:31
合計ジャッジ時間 47,460 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int g=3;
const int N=6e5+10;
const int mod=998244353;
const int lim=8e4+10;
typedef vector<int> poly;
int rev[N],inv[N],a[N],b[N],dp[N],dp1[N],ans[N];
int fac[N];
long long m;
int n,k,x,y,s,len,d;
int mul(int x,int y){return 1ll*x*y%mod;}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x-y>=0?x-y:x-y+mod;}
int ksm(int x,int y){
	ll ans=1;
	for (;y;y>>=1,x=mul(x,x)) if (y&1) ans=mul(ans,x);
	return ans;
}
void init(int x){
	len=1,d=0;
	while (len<x) {len<<=1;d++;}
	for (int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(d-1));
}
inline poly NTT(poly a,int t) {
	for (int i=0;i<a.size();i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
	for (int i=1;i<a.size();i<<=1) {
		int s=(i<<1);
		int wn=ksm(g,(mod-1)/s);
		if (t==-1) wn=ksm(wn,mod-2);
		for (int j=0;j<a.size();j+=s) {
			int w=1;
			for (int k=j;k<j+i;k++) {
				int x=a[k],y=mul(a[k+i],w);
				a[k]=add(x,y); a[k+i]=dec(x,y);
				w=mul(w,wn);
			}
		}
	}
	if (t==-1){
		ll w=ksm(a.size(),mod-2);
		for (int i=0;i<a.size();i++) a[i]=mul(a[i],w);
	}
	return a;
}
inline poly operator +(poly a,poly b){
	a.resize(max(a.size(),b.size()));
	b.resize(max(a.size(),b.size()));
	for (int i=0;i<a.size();i++) a[i]=add(a[i],b[i]);
	return a; 
}
inline poly operator -(poly a,poly b){
	a.resize(max(a.size(),b.size()));
	b.resize(max(a.size(),b.size()));
	for (int i=0;i<a.size();i++) a[i]=dec(a[i],b[i]);
	return a;
}
inline poly operator *(poly a,int x){
	for (int i=0;i<a.size();i++) a[i]=mul(a[i],x);
	return a;
}
inline poly operator *(poly a,poly b){
	int n=a.size(),m=b.size(); 
	init(n+m-1);
	a.resize(len);
	b.resize(len);
	a=NTT(a,1); b=NTT(b,1);
	for (int i=0;i<a.size();i++) a[i]=mul(a[i],b[i]);
	a=NTT(a,-1);
	a.resize(n+m-1);
	return a;
}
int Calc(int x,int y){
	if (x<0||y<0||x<y) return 0;
	return mul(fac[x],mul(inv[y],inv[x-y]));
}
int main(){
	long long B,C;
	scanf("%d%lld%lld",&n,&B,&C);
	fac[0]=1;
	for (int i=1;i<=n;i++) fac[i]=mul(fac[i-1],i);
	inv[0]=inv[1]=1;
	for (int i=2;i<=n;i++) inv[i]=mul(mod-mod/i,inv[mod%i]);
	for (int i=2;i<=n;i++) inv[i]=mul(inv[i-1],inv[i]);
	dp[0]=1;
	for (int k=59;k>=0;k--){
		for (int i=2*n;i>=1;i--) if (i&1) dp[i]=0; else dp[i]=dp[i>>1];
		if ((B>>k)&1ll){
			for (int i=2*n;i>=1;i--) dp[i]=dp[i-1];
			dp[0]=0;
		}
		poly a,b;
		for (int i=0;i<=2*n;i++) a.push_back(dp[i]);
		for (int i=0;i<=n;i++) if (((n-i)&1)==((C>>k)&1ll)) b.push_back(Calc(n,i)); else b.push_back(0);
		a=a*b;
		for (int i=n;i<=3*n;i++) dp[i-n]=a[i];
	}  
 	printf("%d\n",dp[0]);
}
0