QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#43718#2834. Nonsenseaurelion_solRE 241ms19588kbC++142.5kb2022-08-10 11:59:342022-08-10 11:59:35

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-10 11:59:35]
  • 评测
  • 测评结果:RE
  • 用时:241ms
  • 内存:19588kb
  • [2022-08-10 11:59:34]
  • 提交

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)
*/

详细

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

output:


result: