QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#55892 | #2834. Nonsense | foreverlasting# | WA | 26ms | 101872kb | C++17 | 3.3kb | 2022-10-15 15:43:48 | 2022-10-15 15:43:51 |
Judging History
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==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: 7ms
memory: 101816kb
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: 26ms
memory: 101872kb
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'