QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#451358#2834. Nonsensegrass8cowTL 2ms6044kbC++171.3kb2024-06-23 09:09:552024-06-23 09:09:57

Judging History

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

  • [2024-06-23 09:09:57]
  • 评测
  • 测评结果:TL
  • 用时:2ms
  • 内存:6044kb
  • [2024-06-23 09:09:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int qpow(int a,int b){
    int c=1;
    for(;b;b>>=1){
        if(b&1)c=1ll*a*c%mod;
        a=1ll*a*a%mod;
    }
    return c;
}
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int jc[10010],ij[10010],he[10010];
int N,x,y,q,f[5010][5010];
int A[200010],B[200100],n,m;
int main(){
    jc[0]=ij[0]=1;
    for(int i=1;i<=10000;i++)jc[i]=1ll*i*jc[i-1]%mod,ij[i]=qpow(jc[i],mod-2);
    while(~scanf("%d%d%d%d",&N,&x,&y,&q)){
        n=m=0;
        for(int i=1;i<=q;i++)scanf("%d%d",&A[i],&B[i]),n=max(n,A[i]),m=max(m,B[i]);
        for(int i=0,z=1;i<=n+m;i++){
            if(i)z=1ll*z*(N+2-i)%mod;
            he[i]=1ll*z*ij[i]%mod;
        }
        if(x==y){
            for(int i=1;i<=q;i++)
            printf("%d\n",1ll*qpow(x,n-A[i]-B[i])*he[A[i]+B[i]]%mod);
            continue;
        }
        int I=(qpow(x-y,mod-2)+mod)%mod;
        for(int i=0;i<=n;i++)for(int j=0;j<=m;j++){
            f[i][j]=0;
            if(j)ad(f[i][j],f[i][j-1]);
            else ad(f[i][j],1ll*qpow(x,N+1-i)*he[i]%mod);
            if(i)ad(f[i][j],mod-f[i-1][j]);
            else ad(f[i][j],mod-1ll*qpow(y,N+1-j)*he[j]%mod);
            f[i][j]=1ll*f[i][j]*I%mod;
        }
        for(int i=1;i<=q;i++)printf("%d\n",f[A[i]][B[i]]);
    }
    return 0;
}

詳細信息

Test #1:

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

input:

3 1 2 2
1 1
1 2
100 2 3 1
1 1

output:

6
1
866021789

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

1000000000 0 1 1
1000 1000
2 0 0 1
1 1
2 998244352 998244352 1
1 1

output:


result: