QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#55897#2834. Nonsenseforeverlasting#WA 76ms101920kbC++173.7kb2022-10-15 15:54:132022-10-15 15:54:14

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-15 15:54:14]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:101920kb
  • [2022-10-15 15:54:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define gc getchar
#define pb push_back
#define fi first
#define se second
#define Pair pair<int,int>
inline int read(){
	int s=0,w=1,ch=gc();
	while(ch<'0'||ch>'9'){
		if(ch=='-')w=-1;
		ch=gc();
	}
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
	return s*w;
}
template<int kcz>
struct ModInt {
#define T (*this)
	int x;
	ModInt() : x(0) {}
	ModInt(int y) : x(y >= 0 ? y : y + kcz) {}
	ModInt(LL y) : x(y >= 0 ? y % kcz : (kcz - (-y) % kcz) % kcz) {}
	inline int inc(const int &v) {
		return v >= kcz ? v - kcz : v;
	}
	inline int dec(const int &v) {
		return v < 0 ? v + kcz : v;
	}
	inline ModInt &operator+=(const ModInt &p) {
		x = inc(x + p.x);
		return T;
	}
	inline ModInt &operator-=(const ModInt &p) {
		x = dec(x - p.x);
		return T;
	}
	inline ModInt &operator*=(const ModInt &p) {
		x = (int)((LL)x * p.x % kcz);
		return T;
	}
	inline ModInt inverse() const {
		int a = x, b = kcz, u = 1, v = 0, t;
		while (b > 0)t = a / b, swap(a -= t * b, b), swap(u -= t * v, v);
		return u;
	}
	inline ModInt &operator/=(const ModInt &p) {
		T *= p.inverse();
		return T;
	}
	inline ModInt operator-() const {
		return -x;
	}
	inline friend ModInt operator+(const ModInt &lhs, const ModInt &rhs) {
		return ModInt(lhs) += rhs;
	}
	inline friend ModInt operator-(const ModInt &lhs, const ModInt &rhs) {
		return ModInt(lhs) -= rhs;
	}
	inline friend ModInt operator*(const ModInt &lhs, const ModInt &rhs) {
		return ModInt(lhs) *= rhs;
	}
	inline friend ModInt operator/(const ModInt &lhs, const ModInt &rhs) {
		return ModInt(lhs) /= rhs;
	}
	inline bool operator==(const ModInt &p) const {
		return x == p.x;
	}
	inline bool operator!=(const ModInt &p) const {
		return x != p.x;
	}
	ModInt qpow(LL n) const {
		ModInt ret(1), mul(x);
		while (n > 0) {
			if (n & 1)ret *= mul;
			mul *= mul, n >>= 1;
		}
		return ret;
	}
	inline friend ostream &operator<<(ostream &os, const ModInt &p) {
		return os << p.x;
	}
	inline friend istream &operator>>(istream &is, ModInt &a) {
		LL t;
		is >> t, a = ModInt<kcz>(t);
		return is;
	}
	static int get_mod() {
		return kcz;
	}
#undef T
};
const int kcz=998244353;
using Z = ModInt<kcz>;
const int N=5e3+10;
Z f[N][N],g[N*2];
inline void solve(){
	int n,q;
	Z x,y;
	while(scanf("%d%d%d%d",&n,&x,&y,&q)==4){
		int A=0,B=0;
		vector<Pair> que;
		for(int i=1;i<=q;i++){
			int a=read(),b=read();
			que.emplace_back(a,b),A=max(A,a),B=max(B,b);
		}
		if(x==0){
			for(int a=0;a<=A;a++){
				f[a][0]=y.qpow(n-a);
				for(int b=1;b<=B;b++){
					f[a][b]=f[a][b-1]*Z(n-a-b+1)/Z(b)/y;
				}
			}
			for(auto [a,b]:que){
				printf("%d\n",f[a][b]);
			}
			continue;
		}
		if(y==0){
			for(int b=0;b<=B;b++){
				f[0][b]=x.qpow(n-b);
				for(int a=1;a<=A;a++){
					f[a][b]=f[a-1][b]*Z(n-a-b+1)/Z(a)/x;
				}
			}
			for(auto [a,b]:que){
				printf("%d\n",f[a][b]);
			}
			continue;
		}
		if(x==y){
			g[0]=x.qpow(n)*Z((n+1)%kcz);
			for(int i=1;i<=A+B;i++)g[i]=g[i-1]*(x.inverse())*Z(n+1-i)*(Z(i+1).inverse());
			for(auto [a,b]:que){
				printf("%d\n",g[a+b]);
			}
			continue;
		}
		Z inv=(y-x).inverse();
		f[0][0]=(y.qpow(n+1)-x.qpow(n+1))*inv;
		Z C=1;
		for(int i=1;i<=A;i++){
			C*=Z(n+2-i),C/=Z(i);
			f[i][0]=-C*(x.qpow(n+1-i));
			f[i][0]+=f[i-1][0];
			f[i][0]*=inv;
		}
		C=1;
		for(int i=1;i<=B;i++){
			C*=Z(n+2-i),C/=Z(i);
			f[0][i]=C*(y.qpow(n+1-i));
			f[0][i]-=f[0][i-1];
			f[0][i]*=inv;
		}
		for(int i=1;i<=A;i++){
			for(int j=1;j<=B;j++){
				f[i][j]=(f[i-1][j]-f[i][j-1])*inv;
			}
		}
		for(auto [a,b]:que){
			printf("%d\n",f[a][b]);
		}
	}
}
int main(){
	int T=1;
	while(T--)solve();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 101744kb

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
Wrong Answer
time: 76ms
memory: 101920kb

input:

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

output:

381781645
0
1

result:

wrong answer 2nd lines differ - expected: '1', found: '0'