QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#343476#8006. Dinosaur Bones Diggingucup-team1525#WA 6ms12044kbC++178.5kb2024-03-02 17:14:452024-03-02 17:14:46

Judging History

你现在查看的是最新测评结果

  • [2024-03-02 17:14:46]
  • 评测
  • 测评结果：WA
  • 用时：6ms
  • 内存：12044kb
查看
  • [2024-03-02 17:14:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
const int N=1<<19;
const int mod=998244353;
using arr=int[N+5];
int add(int x,int y){ return (x+=y)>=mod?x-mod:x; }
int sub(int x,int y){ return (x-=y)<0?x+mod:x; }
int red(int &x){ return x+=(x>>31)&mod; }
int ksm(ll x,int tp,int s=1){
    for(;tp;x=x*x%mod,tp>>=1) if(tp&1) s=x*s%mod;
    return s;
}
arr fac,ifac,inv;
void prep(){
    fac[0]=ifac[0]=1;
    for(int i=1;i<=N;i++) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[N]=ksm(fac[N],mod-2);
    for(int i=N;i;i--) ifac[i-1]=1ll*ifac[i]*i%mod;
    for(int i=1;i<=N;i++) inv[i]=1ll*ifac[i]*fac[i-1]%mod;
}
namespace poly{
    int L,iv;
    arr w,rev;
    arr pa,pb;
    #define szf sizeof(int)
    void cl(arr a){ memset(a,0,L*szf); }
    void r_prep(){
        int L=N>>1;
        int val=ksm(3,(mod-1)/N);
        w[L]=1;
        for(int i=1;i<L;i++) w[i+L]=1ll*w[i+L-1]*val%mod;
        for(int i=L-1;i;i--) w[i]=w[i<<1];
    }
    void pre_n(int n){
        L=1; while(L<n) L<<=1;
        iv=mod-(mod-1)/L;
        for(int i=1;i<L;i++) rev[i]=(rev[i>>1]>>1)|(i&1?L>>1:0);
    }
    void FFT(arr t,bool ok=1){
        int x,y;
        for(int i=1;i<L;i++)
            if(i<rev[i]) swap(t[i],t[rev[i]]);
        for(int i=1;i<L;i<<=1)
            for(int j=0;j<L;j+=i<<1)
                for(int l=0;l<i;l++){
                    x=t[j+l],y=1ll*t[i+j+l]*w[i+l]%mod;
                    t[i+j+l]=sub(x,y),t[j+l]=add(x,y);
                }
        if(!ok){
            reverse(t+1,t+L);
            for(int i=0;i<L;i++) t[i]=1ll*t[i]*iv%mod;
        }
    }
    void NTT(arr a){ FFT(a); }
    void INTT(arr a){ FFT(a,0); }
    void NTT(arr a,arr b){ memcpy(b,a,L*szf); FFT(b); }
    void INTT(arr a,arr b){ memcpy(b,a,L*szf); FFT(b,0); }
    
    void Mult(arr a,arr b,arr c,int n){
        pre_n(n);
        NTT(a,pa); NTT(b,pb);
        for(int i=0;i<L;i++) c[i]=1ll*pa[i]*pb[i]%mod;
        INTT(c);
        fill(c+n,c+L,0);
        cl(pa); cl(pb);
    }
}
int n;
arr f0,f1,f1f0,f02;
arr ef1,ef1f0,ivf0,ef02;

void solve(int l,int r){
    // fprintf(stderr,"%d %d\n",l,r);
    if(l+1==r){
        if(l>0){
            ef1[l]=add(1ll*ef1[l]*inv[l]%mod,f1[l]);
            ef1f0[l]=add(1ll*ef1f0[l]*inv[l]%mod,f1f0[l]);
            ef02[l]=add(ef02[l],f02[l]);
            ivf0[l]=add(ivf0[l],f0[l]);
        }
        printf("%d: %d %d %d %d %d %d %d\n",l,f0[l],f1[l],f02[l],ivf0[l],ef1[l],ef1f0[l],ef02[l]);
        return;
    }
    int mid=l+r>>1;
    solve(l,mid);
    // fprintf(stderr,"%d %d\n",l,r);
    if(!l){
        int L1=mid-l,L=r-l;
        static arr ta,tb,tc;
        memcpy(ta,f0,L1*sizeof(int));
        memcpy(tb,f1,L1*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            f1f0[j]=add(f1f0[j],tc[j]);
        poly::Mult(ta,ta,tc,L);
        for(int j=mid;j<r;j++)
            f02[j]=add(f02[j],tc[j]);
        memcpy(tb,ivf0,L1*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ivf0[j]=add(ivf0[j],tc[j]);
        for(int j=0;j<L1;j++)
            ta[j]=sub(ef1[j],ef1f0[j]);
        poly::Mult(ta,tb,tc,L);
        for(int j=mid-1;j+1<r;j++)
            f0[j+1]=add(f0[j+1],tc[j]);
        for(int j=0;j<L1;j++)
            ta[j]=sub(ef1[j],ef02[j]);
        poly::Mult(ta,tb,tc,L);
        for(int j=mid-1;j+1<r;j++)
            f1[j+1]=add(f1[j+1],tc[j]);
        memcpy(ta,ef02,L1*sizeof(int));
        memcpy(tb,ef1f0,L1*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ef02[j]=add(ef02[j],tc[j]);
        for(int j=0;j<L1;j++)
            ta[j]=1ll*j*f1f0[j]%mod;
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ef1f0[j]=add(ef1f0[j],tc[j]);
        for(int j=0;j<L1;j++)
            ta[j]=1ll*j*f1[j]%mod;
        memcpy(tb,ef1,L1*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ef1[j]=add(ef1[j],tc[j]);
        // printf("%d\n",ef1[1]);
        memset(ta,0,L*sizeof(int));
        memset(tb,0,L*sizeof(int));
        memset(tc,0,L*sizeof(int));
    }
    else{
        // printf("%d\n",f1[3]);
        int L1=mid-l,L=r-l;
        static arr ta,tb,tc;
        memcpy(ta,f0+l,L1*sizeof(int));
        memcpy(tb,f1,L*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            f1f0[j]=add(f1f0[j],tc[j-l]);
        memcpy(ta,f1+l,L1*sizeof(int));
        memcpy(tb,f0,L*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            f1f0[j]=add(f1f0[j],tc[j-l]);
        memcpy(ta,f0+l,L1*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            f02[j]=add(f02[j],add(tc[j-l],tc[j-l]));
        memcpy(tb,ivf0,L*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ivf0[j]=add(ivf0[j],tc[j-l]);
        memcpy(ta,ivf0+l,L1*sizeof(int));
        memcpy(tb,f0,L*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ivf0[j]=add(ivf0[j],tc[j-l]);
        for(int j=0;j<L;j++)
            tb[j]=sub(ef1[j],ef1f0[j]);
        poly::Mult(ta,tb,tc,L);
        for(int j=mid-1;j+1<r;j++)
            f0[j+1]=add(f0[j+1],tc[j-l]);
        for(int j=0;j<L;j++)
            tb[j]=sub(ef1[j],ef02[j]);
        poly::Mult(ta,tb,tc,L);
        for(int j=mid-1;j+1<r;j++)
            f1[j+1]=add(f1[j+1],tc[j-l]);
        for(int j=l;j<mid;j++)
            ta[j-l]=sub(ef1[j],ef1f0[j]);
        memcpy(tb,ivf0,L*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid-1;j+1<r;j++)
            f0[j+1]=add(f0[j+1],tc[j-l]);
        for(int j=l;j<mid;j++)
            ta[j-l]=sub(ef1[j],ef02[j]);
        poly::Mult(ta,tb,tc,L);
        for(int j=mid-1;j+1<r;j++)
            f1[j+1]=add(f1[j+1],tc[j-l]);
        memcpy(ta,ef1f0+l,L1*sizeof(int));
        memcpy(tb,f02,L*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ef02[j]=add(ef02[j],tc[j-l]);
        memcpy(ta,f02+l,L1*sizeof(int));
        memcpy(tb,ef1f0,L*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ef02[j]=add(ef02[j],tc[j-l]);
        for(int j=l;j<mid;j++)
            ta[j-l]=1ll*j*f1[j]%mod;
        memcpy(tb,ef1,L*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ef1[j]=add(ef1[j],tc[j-l]);
        memcpy(ta,ef1+l,L1*sizeof(int));
        for(int j=0;j<L;j++)
            tb[j]=1ll*j*f1[j]%mod;
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ef1[j]=add(ef1[j],tc[j-l]);
        for(int j=l;j<mid;j++)
            ta[j-l]=1ll*j*f1f0[j]%mod;
        memcpy(tb,ef1f0,L*sizeof(int));
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ef1f0[j]=add(ef1f0[j],tc[j-l]);
        memcpy(ta,ef1f0+l,L1*sizeof(int));
        for(int j=0;j<L;j++)
            tb[j]=1ll*j*f1f0[j]%mod;
        poly::Mult(ta,tb,tc,L);
        for(int j=mid;j<r;j++)
            ef1f0[j]=add(ef1f0[j],tc[j-l]);
        memset(ta,0,L*sizeof(int));
        memset(tb,0,L*sizeof(int));
        memset(tc,0,L*sizeof(int));

    }
    solve(mid,r);
}
int main(){
    scanf("%d",&n);
    prep();
    poly::r_prep();
    int L=0;
    while(n>>L) L++;
    ef1[0]=ef1f0[0]=ivf0[0]=1;
    solve(0,1<<L);
    printf("ans1: %lld\n",1ll*add(f1[n],f0[n])*fac[n]%mod);

    f1[1]=1;
    // memset(f0,0,sizeof f0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++)
            f1f0[i]=(f1f0[i]+1ll*f1[j]*f0[i-j])%mod;
        for(int j=1;j<=i;j++)
            f02[i]=(f02[i]+1ll*f0[j]*f0[i-j])%mod;
        for(int j=1;j<=i;j++)
            ivf0[i]=(ivf0[i]+1ll*f0[j]*ivf0[i-j])%mod;
        
        for(int j=1;j<=i;j++)
            ef1[i]=(ef1[i]+1ll*j*f1[j]%mod*ef1[i-j])%mod;
        ef1[i]=1ll*ef1[i]*inv[i]%mod;
        for(int j=1;j<=i;j++)
            ef1f0[i]=(ef1f0[i]+1ll*j*f1f0[j]%mod*ef1f0[i-j])%mod;
        ef1f0[i]=1ll*ef1f0[i]*inv[i]%mod;
        for(int j=1;j<=i;j++)
            ef02[i]=(ef02[i]+1ll*f02[j]*ef1f0[i-j])%mod;
        for(int j=0;j<=i;j++)
            f0[i+1]=(f0[i+1]+1ll*(ef1[j]-ef1f0[j])*ivf0[i-j])%mod;
        for(int j=0;j<=i;j++)
            f1[i+1]=(f1[i+1]+1ll*(ef1[j]-ef02[j])*ivf0[i-j])%mod;
    
        red(f0[i+1]); red(f1[i+1]);
        printf("%d: %d %d %d %d %d %d %d\n",i,f0[i],f1[i],f02[i],ivf0[i],ef1[i],ef1f0[i],ef02[i]);
    }
    printf("%lld\n",1ll*add(f1[n],f0[n])*fac[n]%mod);
    return 0;  
}
源文件, 语言: C++17

詳細信息

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 12044kb

input:

6
3 5 2 7 4 6
2
1 5
3 6

output:

0: 0 0 0 1 1 1 0
1: 0 1 0 0 1 0 0
2: 1 1 0 1 499122178 0 0
3: 499122178 499122179 0 499122178 665496239 1 0
4: 665496239 166374065 1 665496240 956650848 499122179 1
5: 457528672 623902737 3 457528675 565671827 665496243 3
6: 981606976 108143186 83187039 66549663 625289251 41593539 83187039
7: 500508...

result:

wrong output format 0: is not a valid integer
English 繁體中文 简体中文

伺服器時間: 2025-01-20 22:47:13 | 開源專案