QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#424082 | #2834. Nonsense | CharlieVinnie | TL | 140ms | 101860kb | C++20 | 3.7kb | 2024-05-28 21:39:09 | 2024-05-28 21:39:10 |
Judging History
answer
#include "bits/stdc++.h"
#ifdef DEBUG
#include "PrettyDebug.hpp"
#else
#define debug(...) [](){}()
#define debuga(...) [](){}()
#endif
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std; typedef long long ll;
constexpr int N=5e3+5,mod=998244353;
namespace ModInt{
int qpow(int x,int y){int res=1;while(y){if(y&1)res=1ll*res*x%mod;x=1ll*x*x%mod;y>>=1;}return res;}
class Int{
int x;
public:
explicit Int(int _x=0) : x(_x) {}
Int& operator+= (const Int& O) { unsigned t=x+O.x; x=min(t,t-mod); return *this; }
Int& operator-= (const Int& O) { unsigned t=x-O.x; x=min(t,t+mod); return *this; }
Int& operator*= (const Int& O) { x=1ll*x*O.x%mod; return *this; }
Int operator- () { return Int(x==0?0:mod-x); }
friend Int operator+ (Int A,const Int& B) { return A+=B; }
friend Int operator- (Int A,const Int& B) { return A-=B; }
friend Int operator* (Int A,const Int& B) { return A*=B; }
friend Int inv(const Int& A) { return Int(qpow(A.x,mod-2)); }
template<class ...Args> void add(const Int& A,const Int& B,Args... rest) { add(rest...,Int(1ll*A.x*B.x%mod)); }
void add(const Int& A,const Int& B) { x=(x+1ll*A.x*B.x)%mod; }
template<class ...Args> friend Int mul(const Int& A,const Int& B,Args... rest) { return mul(rest...,Int(1ll*A.x*B.x%mod)); }
Int mul(const Int& A,const Int& B) { return Int(1ll*A.x*B.x%mod); }
friend istream& operator>> (istream& os,Int& O) { return os>>O.x; }
friend ostream& operator<< (ostream& os,const Int& O){
constexpr int LIM=1000;
if(O.x<=LIM) os<<O.x;
else if(O.x>=mod-LIM) os<<O.x<<"(-"<<mod-O.x<<")";
else{
int found=0;
For(v,1,LIM){
int iv=qpow(v,mod-2);
For(u,1,LIM) if(1ll*u*iv%mod==O.x) { found=1; os<<O.x<<'('<<u<<"/"<<v<<')'; goto OUT; }
For(u,1,LIM) if(mod-1ll*u*iv%mod==O.x) { found=1; os<<O.x<<"(-"<<u<<"/"<<v<<')'; goto OUT; }
}
OUT: if(!found) os<<O.x<<"(?)";
}
return os;
}
friend Int qpow(Int x,int y) { return Int(qpow(x.x,y)); }
friend Int ID(Int x) { return x.x&1?Int(mod-1):Int(1); }
int operator()() const { return x; }
};
Int ID(int x) { return x&1?Int(mod-1):Int(1); }
Int Norm(ll x) { unsigned t=x%mod; return Int(min(t,t+mod)); }
}
using namespace ModInt;
int n,Q; Int X,Y,C[N*2],pwX[N],pwY[N],f[N][N];
signed main(){
atexit([](){cerr<<"Time = "<<clock()<<" ms"<<endl;});
while(cin>>n>>X>>Y>>Q){
vector<pair<int,int>> qry(Q); int lim=0;
for(auto& [i,j]:qry) cin>>i>>j,lim=max(lim,max(i,j));
C[0]=Int(1); For(i,1,lim*2+1) C[i]=C[i-1]*inv(Int(i))*Int(n-i+2);
pwX[0]=qpow(X,n+1); For(i,1,lim) pwX[i]=pwX[i-1]*inv(X);
pwY[0]=qpow(Y,n+1); For(i,1,lim) pwY[i]=pwY[i-1]*inv(Y);
if(X()==Y()){
for(auto [a,b]:qry) cout<<(C[a+b+1]*qpow(X,n-a-b))()<<'\n';
continue;
}
For(i,0,lim) For(j,0,lim) {
f[i][j]=Int(0);
if(j>0) f[i][j]+=f[i][j-1]; else f[i][j]+=C[i]*pwX[i];
if(i>0) f[i][j]-=f[i-1][j]; else f[i][j]-=C[j]*pwY[j];
f[i][j]*=inv(X-Y);
}
for(auto [a,b]:qry) cout<<f[a][b]()<<'\n';
}
return 0;
}
// CONTINUE, NON-STOPPING, FOR CHARLIEY
// START TYPING IF YOU DON'T KNOW WHAT TO DO
// STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
// Started Coding On: May 28 Tue, 21 : 06 : 11
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 101820kb
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: 140ms
memory: 101860kb
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
Time Limit Exceeded
input:
1000000000 998244351 998244352 1 5000 5000