QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#19509#1810. Generate the SequencesforeverlastingAC ✓11ms10152kbC++206.4kb2022-02-02 15:04:012022-05-06 05:38:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 05:38:08]
  • 评测
  • 测评结果:AC
  • 用时:11ms
  • 内存:10152kb
  • [2022-02-02 15:04:01]
  • 提交

answer

//2022.2.2 by ljz
//email [email protected]
//if you find any bug in my code
//please tell me
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
#define res int
#define LL long long
#define Inf 0x3f3f3f3f
#define sup 0x7fffffff
#define inf 0x3f3f3f3f
#define INF 2000000000000000000
//#define unl __int128
#define eps 1e-10
#define RG
#define db double
#define pc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
//#define pc(x) __builtin_popcountll(x)
typedef pair<int,int> Pair;
//#define poly vector<int>
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pb push_back
#define ull unsigned LL
#define uint unsigned int
#define lowbit(x) ((x)&-(x))
#define gc getchar
#define ld long db
//template <class T>using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//inline int gc() {
//    static char buf[100000],*p1,*p2;
//    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
//char sr[1<<21],z[20];
//int C=-1,Z=0;
//inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
//inline void print(RG LL x){
//    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;
//    while(z[++Z]=x%10+48,x/=10);
//    while(sr[++C]=z[Z],--Z);
//}
template <typename T> inline void Read(T &x) {
    res c=gc();
    bool f=false;
    for(x=0;!isdigit(c);c=gc())if(c=='-')f=true;
    for(;isdigit(c);c=gc())x=x*10+c-'0';
    if(f)x=-x;
}
inline int read() {
    res s=0,ch=gc(),w=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        else if(ch==EOF)break;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s*w;
}
inline LL Read() {
    RG LL s=0;
    res ch=gc(),w=1;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        else if(ch==EOF)break;
        ch=gc();
    }
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s*w;
}
inline void write(RG __int128 x){
    if(x>10)write(x/10);
    putchar(int(x%10)+'0');
}
const int kcz=998244353;
const int G=3,GI=332748118;
//inline void add(res &x,const res &y){
//    x+=y,x>=kcz?x-=kcz:1;
//}
//inline int Add(const res &x,const res &y){
//    return x+y>=kcz?x+y-kcz:x+y;
//}
//inline int mul(const res &x,const res &y){
//    return int(1ll*x*y%kcz);
//}
#define add(x,y) ((x)+=(y),(x)>=kcz?(x)-=kcz:1)
#define Add(x,y) ((x)+(y)>=kcz?(x)+(y)-kcz:(x)+(y))
#define mul(x,y) (int)((LL)(x)*(y)%kcz)
#define Mul(x,y,d) (int)((ull)(x)*(y)/(d)%kcz)
inline int qpow(res x,res y=kcz-2){
    res ret=1;
    while(y){
        if(y&1)ret=mul(ret,x);
        x=mul(x,x),y>>=1;
    }
    return ret;
}
inline int qpow(res x,res y,const res &ljc){
    res ret=1;
    while(y){
        if(y&1)ret=(int)(1ll*ret*x%ljc);
        x=(int)(1ll*x*x%ljc),y>>=1;
    }
    return ret;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//cloclim_t start=cloclim();
//inline void clim(){
//    if(1.0*(cloclim()-start)/CLOCKS_PER_SEC>0.1)exit(0);
//}
//2022.2.2 by ljz
//email [email protected]
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
    int pos[N],inv[N];
    inline void NTT(res *A,const res &type,const res &lim){
        for(res i=0;i<lim;i++)if(i<pos[i])swap(A[i],A[pos[i]]);
        for(res mid=1;mid<lim;mid<<=1){
            res wn=qpow(type==1?G:GI,(kcz-1)/(mid<<1));
            for(res j=0;j<lim;j+=mid<<1){
                res w=1;
                for(res k=0;k<mid;k++,w=mul(w,wn)){
                    res x=A[j+k],y=mul(w,A[j+mid+k]);
                    A[j+k]=Add(x,y),A[j+mid+k]=Add(x,kcz-y);
                }
            }
        }
        if(type==-1){
            res INV=qpow(lim,kcz-2);
            for(res i=0;i<=lim;i++)A[i]=mul(A[i],INV);
        }
    }
    inline void derivation(const res *A,res *B,const res &lim){
        for(res i=1;i<lim;i++)B[i-1]=mul(i,A[i]);
        B[lim-1]=0;
    }
    inline void integral(const res *A,res *B,const res &lim){
        for(res i=1;i<lim;i++)B[i]=mul(A[i-1],inv[i]);
        B[0]=0;
    }
    int A[N],B[N],D[N],E[N];
    void getinv(res *a,res *b,res lim){
        if(lim==1){b[0]=qpow(a[0]);return;}
        getinv(a,b,lim>>1);
        for(res i=0;i<lim;i++)A[i]=a[i],B[i]=b[i];
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        NTT(A,1,len),NTT(B,1,len);
        for(res i=0;i<len;i++)A[i]=mul(A[i],mul(B[i],B[i]));
        NTT(A,-1,len);
        for(res i=0;i<lim;i++)b[i]=Add(b[i],Add(b[i],kcz-A[i]));
        for(res i=0;i<len;i++)A[i]=B[i]=0;
    }
    inline void getln(res *a,res *b,const res &lim){
        derivation(a,D,lim),getinv(a,E,lim);
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        NTT(D,1,len),NTT(E,1,len);
        for(res i=0;i<len;i++)D[i]=mul(D[i],E[i]);
        NTT(D,-1,len);
        integral(D,b,lim);
        for(res i=0;i<len;i++)D[i]=E[i]=0;
    }
    int F[N],G[N];
    void getexp(res *a,res *b,res lim){
        if(lim==1){b[0]=1;return;}
        getexp(a,b,lim>>1);
        getln(b,G,lim);
        for(res i=0;i<lim;i++)F[i]=b[i],G[i]=Add(kcz-G[i],a[i]);
        G[0]=Add(G[0],1);
        res qaq=0,len=1;
        while(len<=lim)len<<=1,qaq++;
        for(res i=0;i<len;i++)pos[i]=(pos[i>>1]>>1)|((i&1)<<(qaq-1));
        NTT(F,1,len),NTT(G,1,len);
        for(res i=0;i<len;i++)F[i]=mul(F[i],G[i]);
        NTT(F,-1,len);
        for(res i=0;i<lim;i++)b[i]=F[i];
        for(res i=0;i<len;i++)F[i]=G[i]=0;
    }
    int n,m;
    int a[N],b[N];
    inline void MAIN(){
        n=read(),m=read(),inv[0]=inv[1]=1;
        res l=1;
        while(l<=n)l<<=1;
        for(res i=2;i<=l;i++)inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        a[0]=1;
        for(res i=1;i<=min(l,m-2);i++)a[i]=mul(a[i-1],mul(inv[i],m-1-i));
        integral(a,b,l);
        b[1]++,getexp(b,a,l);
        res fac=1;
        for(res i=1;i<=n;i++)fac=mul(fac,i);
        printf("%d\n",mul(fac,a[n]));
    }
}
int main(){
//    srand(time(0));
//    freopen("18_linked_list.in","r",stdin);
//    freopen("1.out","w",stdout);
    res Case=1;
    for(res T=1;T<=Case;T++)MAIN::MAIN();
//    Ot();
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 9908kb

input:

2 3

output:

5

result:

ok answer is '5'

Test #2:

score: 0
Accepted
time: 0ms
memory: 10016kb

input:

1024 52689658

output:

654836147

result:

ok answer is '654836147'

Test #3:

score: 0
Accepted
time: 0ms
memory: 9920kb

input:

1 2

output:

2

result:

ok answer is '2'

Test #4:

score: 0
Accepted
time: 4ms
memory: 9940kb

input:

1 3

output:

2

result:

ok answer is '2'

Test #5:

score: 0
Accepted
time: 1ms
memory: 9892kb

input:

1 100000000

output:

2

result:

ok answer is '2'

Test #6:

score: 0
Accepted
time: 0ms
memory: 9864kb

input:

2 2

output:

4

result:

ok answer is '4'

Test #7:

score: 0
Accepted
time: 4ms
memory: 9852kb

input:

2 4

output:

6

result:

ok answer is '6'

Test #8:

score: 0
Accepted
time: 0ms
memory: 9940kb

input:

2 5

output:

7

result:

ok answer is '7'

Test #9:

score: 0
Accepted
time: 4ms
memory: 9908kb

input:

2 100000000

output:

100000002

result:

ok answer is '100000002'

Test #10:

score: 0
Accepted
time: 2ms
memory: 9972kb

input:

3 2

output:

8

result:

ok answer is '8'

Test #11:

score: 0
Accepted
time: 3ms
memory: 9900kb

input:

3 3

output:

14

result:

ok answer is '14'

Test #12:

score: 0
Accepted
time: 4ms
memory: 9852kb

input:

3 4

output:

22

result:

ok answer is '22'

Test #13:

score: 0
Accepted
time: 4ms
memory: 9908kb

input:

3 5

output:

32

result:

ok answer is '32'

Test #14:

score: 0
Accepted
time: 4ms
memory: 9976kb

input:

3 100000000

output:

446563791

result:

ok answer is '446563791'

Test #15:

score: 0
Accepted
time: 10ms
memory: 10076kb

input:

3000 2

output:

21292722

result:

ok answer is '21292722'

Test #16:

score: 0
Accepted
time: 5ms
memory: 9952kb

input:

3000 3

output:

172222927

result:

ok answer is '172222927'

Test #17:

score: 0
Accepted
time: 3ms
memory: 10152kb

input:

3000 100000000

output:

736503947

result:

ok answer is '736503947'

Test #18:

score: 0
Accepted
time: 11ms
memory: 10000kb

input:

2522 61077387

output:

857454425

result:

ok answer is '857454425'

Test #19:

score: 0
Accepted
time: 2ms
memory: 9948kb

input:

426 7215704

output:

799491736

result:

ok answer is '799491736'

Test #20:

score: 0
Accepted
time: 6ms
memory: 9880kb

input:

772 72289915

output:

848141383

result:

ok answer is '848141383'

Test #21:

score: 0
Accepted
time: 3ms
memory: 9936kb

input:

1447 83321470

output:

160422285

result:

ok answer is '160422285'

Test #22:

score: 0
Accepted
time: 7ms
memory: 9936kb

input:

2497 64405193

output:

355300540

result:

ok answer is '355300540'

Test #23:

score: 0
Accepted
time: 2ms
memory: 9956kb

input:

775 9385367

output:

470172346

result:

ok answer is '470172346'

Test #24:

score: 0
Accepted
time: 3ms
memory: 9948kb

input:

982 72596758

output:

7144187

result:

ok answer is '7144187'

Test #25:

score: 0
Accepted
time: 5ms
memory: 9920kb

input:

417 26177178

output:

776374896

result:

ok answer is '776374896'

Test #26:

score: 0
Accepted
time: 2ms
memory: 9988kb

input:

1932 19858856

output:

285834553

result:

ok answer is '285834553'

Test #27:

score: 0
Accepted
time: 5ms
memory: 10096kb

input:

2728 23009122

output:

433516287

result:

ok answer is '433516287'

Test #28:

score: 0
Accepted
time: 3ms
memory: 9984kb

input:

1857 22578508

output:

243488639

result:

ok answer is '243488639'

Test #29:

score: 0
Accepted
time: 7ms
memory: 10112kb

input:

2918 69623276

output:

546299707

result:

ok answer is '546299707'

Test #30:

score: 0
Accepted
time: 7ms
memory: 10000kb

input:

1679 21332149

output:

217000656

result:

ok answer is '217000656'

Test #31:

score: 0
Accepted
time: 7ms
memory: 9916kb

input:

1340 6251797

output:

267221018

result:

ok answer is '267221018'

Test #32:

score: 0
Accepted
time: 3ms
memory: 9928kb

input:

868 64770398

output:

652067665

result:

ok answer is '652067665'