QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#424082#2834. NonsenseCharlieVinnieTL 140ms101860kbC++203.7kb2024-05-28 21:39:092024-05-28 21:39:10

Judging History

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

  • [2024-05-28 21:39:10]
  • 评测
  • 测评结果:TL
  • 用时:140ms
  • 内存:101860kb
  • [2024-05-28 21:39:09]
  • 提交

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

output:


result: