QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#99426#6323. Range NEQGeorge_Plover#AC ✓1131ms30000kbC++232.5kb2023-04-22 13:54:392023-04-22 13:54:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-22 13:54:43]
  • 评测
  • 测评结果:AC
  • 用时:1131ms
  • 内存:30000kb
  • [2023-04-22 13:54:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define wln putchar('\n')
const int N=1005,M=1000005,MOD=998244353,N2=1<<20,G=3;
int sqr(int x){return 1ll*x*x%MOD;}
int mo(int x){return x>=MOD?x-MOD:x;}
void moplus(int &x,int y){x=mo(x+y);}
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1)res=1ll*res*a%MOD;
        a=1ll*a*a%MOD;
        b>>=1;
    }
    return res;
}
int fac[M],ifac[M];
void math_init(int n)
{
    fac[0]=1;
    For(i,1,n)fac[i]=1ll*fac[i-1]*i%MOD;
    ifac[n]=ksm(fac[n],MOD-2);
    Rof(i,n,1)ifac[i-1]=1ll*ifac[i]*i%MOD;
}
int getC(int a,int b){return 1ll*fac[a]*ifac[b]%MOD*ifac[a-b]%MOD;}
void dft(int n,int a[],int w[])
{
    for(int i=0;(1<<i)<n;i++)
        for(int j=0;j<n;j+=1<<i+1)
            For(k,0,(1<<i)-1)
            {
                int x=a[j+k],y=1ll*w[(n>>i+1)*k]*a[j+(1<<i)+k]%MOD;
                a[j+k]=mo(x+y); a[j+(1<<i)+k]=mo(x-y+MOD);
            }
}
void mul(int n,int a[],int b[])
{
    static int r[N2],w[N2>>1];
    int invn=ksm(n,MOD-2);
    r[0]=0;
    For(i,1,n-1)
    {
        r[i]=r[i>>1]>>1|(i&1)*(n>>1);
        if(r[i]<i)swap(a[r[i]],a[i]),swap(b[r[i]],b[i]);
    }
    w[0]=1; w[1]=ksm(G,(MOD-1)/n);
    For(i,2,(n>>1)-1)w[i]=1ll*w[i-1]*w[1]%MOD;
    dft(n,a,w); dft(n,b,w);
    For(i,0,n-1)
    {
        a[i]=1ll*a[i]*b[i]%MOD;
        if(r[i]<i)swap(a[r[i]],a[i]);
    }
    dft(n,a,w);
    reverse(a+1,a+n);
    For(i,0,n-1)a[i]=1ll*a[i]*invn%MOD;
}
void mul(int &lena,int a[],int lenb,int b[])
{
    int n=1;
    while(n<lena+lenb-1)n<<=1;
    fill(a+lena,a+n,0);
    fill(b+lenb,b+n,0);
    mul(n,a,b);
    while(n&&a[n-1]==0)n--;
    lena=n;
}
int n,m,a[N2],lena,b[N2],lenb,c[N2];
int main()
{
    scanf("%d%d",&n,&m);
    math_init(n*m);
    For(i,0,m)a[i]=1ll*sqr(getC(m,i))*fac[i]%MOD;
    lena=m+1; lenb=1;
    b[0]=1;
    int x=n;
    while(x)
    {
        if(x&1)
        {
            copy(a,a+lena,c);
            mul(lenb,b,lena,c);
        }
        copy(a,a+lena,c);
        mul(lena,a,lena,c);
        x>>=1;
        // printf("a:");
        // For(i,0,lena-1)printf("%d ",a[i]); wln;
        // printf("b:");
        // For(i,0,lenb-1)printf("%d ",b[i]); wln;
    }
    //printf("qwq\n");
    int res=0;
    For(i,0,n*m)
    {
        int s=1ll*b[i]*fac[n*m-i]%MOD;
        if(i&1)moplus(res,MOD-s);
        else moplus(res,s);
    }
    printf("%d",res);
}

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 15808kb

input:

2 2

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

5 1

output:

44

result:

ok 1 number(s): "44"

Test #3:

score: 0
Accepted
time: 16ms
memory: 15920kb

input:

167 91

output:

284830080

result:

ok 1 number(s): "284830080"

Test #4:

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

input:

2 1

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

2 3

output:

36

result:

ok 1 number(s): "36"

Test #6:

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

input:

2 4

output:

576

result:

ok 1 number(s): "576"

Test #7:

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

input:

3 1

output:

2

result:

ok 1 number(s): "2"

Test #8:

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

input:

3 2

output:

80

result:

ok 1 number(s): "80"

Test #9:

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

input:

3 3

output:

12096

result:

ok 1 number(s): "12096"

Test #10:

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

input:

3 4

output:

4783104

result:

ok 1 number(s): "4783104"

Test #11:

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

input:

4 1

output:

9

result:

ok 1 number(s): "9"

Test #12:

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

input:

4 2

output:

4752

result:

ok 1 number(s): "4752"

Test #13:

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

input:

4 3

output:

17927568

result:

ok 1 number(s): "17927568"

Test #14:

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

input:

4 4

output:

776703752

result:

ok 1 number(s): "776703752"

Test #15:

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

input:

5 2

output:

440192

result:

ok 1 number(s): "440192"

Test #16:

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

input:

5 3

output:

189125068

result:

ok 1 number(s): "189125068"

Test #17:

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

input:

5 4

output:

975434093

result:

ok 1 number(s): "975434093"

Test #18:

score: 0
Accepted
time: 1131ms
memory: 29988kb

input:

1000 1000

output:

720037464

result:

ok 1 number(s): "720037464"

Test #19:

score: 0
Accepted
time: 8ms
memory: 15880kb

input:

72 42

output:

638177567

result:

ok 1 number(s): "638177567"

Test #20:

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

input:

15 19

output:

663050288

result:

ok 1 number(s): "663050288"

Test #21:

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

input:

68 89

output:

94365047

result:

ok 1 number(s): "94365047"

Test #22:

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

input:

92 37

output:

652605307

result:

ok 1 number(s): "652605307"

Test #23:

score: 0
Accepted
time: 9ms
memory: 16076kb

input:

61 87

output:

498277867

result:

ok 1 number(s): "498277867"

Test #24:

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

input:

81 40

output:

133095344

result:

ok 1 number(s): "133095344"

Test #25:

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

input:

7 91

output:

524164813

result:

ok 1 number(s): "524164813"

Test #26:

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

input:

31 18

output:

361233485

result:

ok 1 number(s): "361233485"

Test #27:

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

input:

74 54

output:

500686087

result:

ok 1 number(s): "500686087"

Test #28:

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

input:

32 2

output:

586504335

result:

ok 1 number(s): "586504335"

Test #29:

score: 0
Accepted
time: 724ms
memory: 29808kb

input:

656 718

output:

346764298

result:

ok 1 number(s): "346764298"

Test #30:

score: 0
Accepted
time: 231ms
memory: 17016kb

input:

254 689

output:

358078813

result:

ok 1 number(s): "358078813"

Test #31:

score: 0
Accepted
time: 758ms
memory: 29992kb

input:

713 674

output:

914437613

result:

ok 1 number(s): "914437613"

Test #32:

score: 0
Accepted
time: 145ms
memory: 21172kb

input:

136 698

output:

56687290

result:

ok 1 number(s): "56687290"

Test #33:

score: 0
Accepted
time: 202ms
memory: 26632kb

input:

369 401

output:

312325811

result:

ok 1 number(s): "312325811"

Test #34:

score: 0
Accepted
time: 68ms
memory: 16540kb

input:

280 204

output:

280012063

result:

ok 1 number(s): "280012063"

Test #35:

score: 0
Accepted
time: 218ms
memory: 16880kb

input:

904 225

output:

162909174

result:

ok 1 number(s): "162909174"

Test #36:

score: 0
Accepted
time: 1049ms
memory: 29768kb

input:

855 928

output:

39885159

result:

ok 1 number(s): "39885159"

Test #37:

score: 0
Accepted
time: 232ms
memory: 16872kb

input:

503 365

output:

745115888

result:

ok 1 number(s): "745115888"

Test #38:

score: 0
Accepted
time: 927ms
memory: 29764kb

input:

646 996

output:

610925577

result:

ok 1 number(s): "610925577"

Test #39:

score: 0
Accepted
time: 1101ms
memory: 29844kb

input:

990 918

output:

203469632

result:

ok 1 number(s): "203469632"

Test #40:

score: 0
Accepted
time: 1085ms
memory: 29768kb

input:

961 949

output:

169566857

result:

ok 1 number(s): "169566857"

Test #41:

score: 0
Accepted
time: 1083ms
memory: 29824kb

input:

946 932

output:

352423195

result:

ok 1 number(s): "352423195"

Test #42:

score: 0
Accepted
time: 1070ms
memory: 29804kb

input:

903 981

output:

196309824

result:

ok 1 number(s): "196309824"

Test #43:

score: 0
Accepted
time: 1079ms
memory: 29748kb

input:

916 988

output:

487208972

result:

ok 1 number(s): "487208972"

Test #44:

score: 0
Accepted
time: 1089ms
memory: 29764kb

input:

982 982

output:

387421488

result:

ok 1 number(s): "387421488"

Test #45:

score: 0
Accepted
time: 1074ms
memory: 29960kb

input:

955 911

output:

955637031

result:

ok 1 number(s): "955637031"

Test #46:

score: 0
Accepted
time: 1065ms
memory: 29804kb

input:

906 999

output:

798469943

result:

ok 1 number(s): "798469943"

Test #47:

score: 0
Accepted
time: 1117ms
memory: 29764kb

input:

982 975

output:

193506289

result:

ok 1 number(s): "193506289"

Test #48:

score: 0
Accepted
time: 1087ms
memory: 30000kb

input:

921 991

output:

431202149

result:

ok 1 number(s): "431202149"