結果
問題 | No.2237 Xor Sum Hoge |
ユーザー |
|
提出日時 | 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 |
ソースコード
#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]); }