結果

問題 No.2237 Xor Sum Hoge
ユーザー no wayno way
提出日時 2023-03-03 22:37:37
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2,768 ms
9,860 KB
testcase_01 AC 8 ms
5,248 KB
testcase_02 AC 8 ms
5,376 KB
testcase_03 AC 8 ms
5,376 KB
testcase_04 AC 14 ms
5,376 KB
testcase_05 AC 28 ms
5,376 KB
testcase_06 AC 14 ms
5,376 KB
testcase_07 AC 14 ms
5,376 KB
testcase_08 AC 14 ms
5,376 KB
testcase_09 AC 15 ms
5,376 KB
testcase_10 AC 28 ms
5,376 KB
testcase_11 AC 291 ms
5,376 KB
testcase_12 AC 1,292 ms
6,528 KB
testcase_13 AC 2,767 ms
9,656 KB
testcase_14 AC 1,313 ms
6,580 KB
testcase_15 AC 638 ms
5,376 KB
testcase_16 AC 1,328 ms
7,400 KB
testcase_17 AC 1,328 ms
6,836 KB
testcase_18 AC 625 ms
5,376 KB
testcase_19 AC 623 ms
5,376 KB
testcase_20 AC 1,304 ms
7,152 KB
testcase_21 AC 2,823 ms
9,684 KB
testcase_22 AC 2,792 ms
9,392 KB
testcase_23 AC 2,761 ms
9,592 KB
testcase_24 AC 2,809 ms
9,832 KB
testcase_25 AC 2,861 ms
9,644 KB
testcase_26 AC 2,715 ms
9,672 KB
testcase_27 AC 2,756 ms
9,680 KB
testcase_28 AC 2,745 ms
9,572 KB
testcase_29 AC 2,783 ms
9,520 KB
testcase_30 AC 2,774 ms
9,756 KB
testcase_31 AC 3 ms
5,376 KB
testcase_32 AC 3 ms
5,376 KB
testcase_33 AC 29 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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