結果

問題 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  
実行時間 3,177 ms / 10,000 ms
コード長 2,563 bytes
コンパイル時間 1,900 ms
コンパイル使用メモリ 177,040 KB
実行使用メモリ 13,132 KB
最終ジャッジ日時 2023-10-18 02:46:58
合計ジャッジ時間 55,214 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3,175 ms
13,132 KB
testcase_01 AC 10 ms
7,892 KB
testcase_02 AC 10 ms
7,888 KB
testcase_03 AC 9 ms
7,892 KB
testcase_04 AC 17 ms
7,912 KB
testcase_05 AC 32 ms
7,956 KB
testcase_06 AC 16 ms
7,912 KB
testcase_07 AC 16 ms
7,912 KB
testcase_08 AC 17 ms
7,924 KB
testcase_09 AC 17 ms
7,924 KB
testcase_10 AC 32 ms
7,956 KB
testcase_11 AC 334 ms
8,344 KB
testcase_12 AC 1,490 ms
10,116 KB
testcase_13 AC 3,172 ms
13,112 KB
testcase_14 AC 1,495 ms
10,396 KB
testcase_15 AC 705 ms
8,760 KB
testcase_16 AC 1,537 ms
10,968 KB
testcase_17 AC 1,516 ms
10,680 KB
testcase_18 AC 722 ms
9,040 KB
testcase_19 AC 717 ms
9,032 KB
testcase_20 AC 1,520 ms
10,680 KB
testcase_21 AC 3,168 ms
13,120 KB
testcase_22 AC 3,164 ms
13,112 KB
testcase_23 AC 3,171 ms
13,128 KB
testcase_24 AC 3,161 ms
13,128 KB
testcase_25 AC 3,161 ms
13,112 KB
testcase_26 AC 3,157 ms
13,120 KB
testcase_27 AC 3,161 ms
13,120 KB
testcase_28 AC 3,169 ms
13,116 KB
testcase_29 AC 3,159 ms
13,112 KB
testcase_30 AC 3,177 ms
13,132 KB
testcase_31 AC 3 ms
7,872 KB
testcase_32 AC 3 ms
7,872 KB
testcase_33 AC 33 ms
7,956 KB
testcase_34 AC 3 ms
7,868 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