QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#43718 | #2834. Nonsense | aurelion_sol | RE | 241ms | 19588kb | C++14 | 2.5kb | 2022-08-10 11:59:34 | 2022-08-10 11:59:35 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a),_=(b);i<=_;++i)
#define per(i,a,b) for(int i=(a),_=(b);i>=_;--i)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define size(x) int(x.size())
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ul;
typedef __int128 LL;
typedef __uint128_t UL;
typedef double db;
typedef vector<int> VI;
const int mod=998244353;
int inc(int x,int y){return x+=y-mod,x+=x>>31&mod;}
int dec(int x,int y){return x-=y,x+=x>>31&mod;}
int mul(int x,int y){return ul(x)*y%mod;}
int inc2(int &x,int y){return x+=y-mod,x+=x>>31&mod;}
int dec2(int &x,int y){return x-=y,x+=x>>31&mod;}
int mul2(int &x,int y){return x=ul(x)*y%mod;}
int qpow(int x,int y){int z=1;for(;y;y>>=1,x=mul(x,x))if(y&1)z=mul(x,z);return z;}
const int N=5010,L=2e5+10;
int T,n,A,B,Q,lim,inv[2*N],f[N][2*N];
struct query{
int a,b;
}qry[L];
void init(int n){
inv[1]=1;
rep(i,2,n)inv[i]=mul(mod-mod/i,inv[mod%i]);
}
int calc(int m,int p,int a){
if(a==1){
int pr=1;
rep(i,0,p)pr=mul(pr,m+1+i);
rep(i,1,p+1)pr=mul(pr,inv[i]);
return pr;
}
static int f[N];
static int g[N];
int num=qpow(a,m+1);
int bin=1;
rep(i,0,p){
if(i>0){
bin=mul(bin,mul(m+i,inv[i]));
}
f[i]=dec(!i,mul(num,bin));
}
int inv=qpow(dec(1,a),mod-2);
int sum=0;
rep(i,0,p){
g[i]=mul(inv,i?g[i-1]:1);
sum=inc(sum,mul(g[i],f[p-i]));
}
return sum;
}
int main(){
init(2*N-10);
while(1){
if(scanf("%d%d%d%d",&n,&A,&B,&Q)!=4)break;
lim=0;
rep(i,1,Q){
scanf("%d%d",&qry[i].a,&qry[i].b);
lim=max(lim,qry[i].a+qry[i].b);
}
if(!A&&!B){
rep(i,1,Q){
puts(qry[i].a+qry[i].b==n?"1":"0");
}
}else{
if(!A){
swap(A,B);
rep(i,1,Q)swap(qry[i].a,qry[i].b);
}
int C=mul(B,qpow(A,mod-2));
rep(q,0,lim){
// if(!B){
// f[0][q]=qpow(A,n-q);
// continue;
// }else{
f[0][q]=mul(qpow(A,n-q),calc(n-q,q,C));
/*
int s=0;
rep(i,0,n-q){
int t=1;
rep(j,0,q-1)t=mul(t,i+q-j);
rep(j,1,q)t=mul(t,qpow(j,mod-2));
s=inc(s,mul(t,qpow(C,i)));
}
cout<<q<<' '<<s<<' '<<calc(n-q,q,C)<<endl;
*/
// }
}
rep(p,0,min(lim,N-10))rep(q,0,lim-1-p){
f[p+1][p+q+1]=mul(qpow(mul(p+1,A),mod-2),dec(mul(n-p-q,f[p][p+q]),mul(mul(q+1,B),f[p][p+q+1])));
}
rep(i,1,Q){
printf("%d\n",f[qry[i].a][qry[i].a+qry[i].b]);
}
}
}
exit(0);
}
/*
(n-p-q)F(n,p,q)=(p+1)a*F(n,p+1,q)+(q+1)b*F(n,p,q+1)
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3896kb
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: 0
Accepted
time: 241ms
memory: 19588kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
381781645 1 1
result:
ok 3 lines
Test #3:
score: -100
Runtime Error
input:
1000000000 998244351 998244352 1 5000 5000