結果

問題 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]);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0