QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#659995 | #9486. Random Mex | ucup-team134# | ML | 0ms | 0kb | C++14 | 3.0kb | 2024-10-20 01:35:26 | 2024-10-20 01:35:27 |
answer
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
int ckmul(int &x,int y){x=mul(x,y);}
int ckadd(int &x,int y){x=add(x,y);}
int powmod(int x,int k){
int ans=1;
for(;k;k>>=1,x=mul(x,x))if(k&1)ans=mul(ans,x);
return ans;
}
int inv(int x){return powmod(x,mod-2);}
int mul_inv(int x){return inv(x);}
void fft(int a[],int n,bool inv){
for(int i=1,j=0;i<n;++i){
int k=n;do j^=k>>=1;while(~j&k);
if(j>i)swap(a[i],a[j]);
}
for(int j=2;j<=n;j<<=1){
int ang=powmod(3,(mod-1)/j);
if(inv)ang=mul_inv(ang);
for(int i=0;i<n/j;++i){
for(int k=i*j,cur=1;k<i*j+j/2;ckmul(cur,ang),++k){
int tmp=mul(cur,a[k+j/2]);
a[k+j/2]=sub(a[k],tmp);
ckadd(a[k],tmp);
}
}
}
if(inv){
int m=mul_inv(n);
for(int i=0;i<n;i++)ckmul(a[i],m);
}
}
const int N=1<<13;
vector<pair<int,int>> Qs[N];
int F[N],I[N];
int binom(int n,int k){
return mul(F[n],mul(I[k],I[n-k]));
}
const int M=300050;
int ans[M];
void mul(int* a,int* b,int* c){
fft(a,N*2,false);
//fft(b,N*2,false);
for(int i=0;i<N*2;i++)c[i]=mul(a[i],b[i]);
fft(c,N*2,true);
for(int i=N;i<N*2;i++)a[i]=0;
}
int dp[N],a[N*2],b[N*2],c[N*2];
//int bdp[N][N];
void Solve(){
F[0]=1;
for(int i=1;i<N;i++)F[i]=mul(F[i-1],i);
I[0]=I[1]=1;
for(int i=2;i<N;i++)I[i]=mul(mod-mod/i,I[mod%i]);
for(int i=1;i<N;i++)I[i]=mul(I[i],I[i-1]);
/*for(int m=1;m<N;m++){
for(int n=1;n<N;n++){
for(int x=1;x<=n;x++){
bdp[m][n]=add(bdp[m][n],mul(add(bdp[m-1][n-x],1),mul(powmod(inv(m),n),mul(binom(n,x),powmod(m-1,n-x)))));
}
//printf("%i ",bdp[m][n]);
}
for(auto qu:Qs[m]){
ans[qu.second]=bdp[m][qu.first];
}
//printf("\n");
}*/
//printf("\n");
for(int n=0;n<N;n++){
b[n]=I[n];
}
b[0]=0;
fft(b,N*2,false);
for(int i=0;i<N;i++)dp[i]=0;
for(int m=1;m<N;m++){
int now=1;
for(int n=0;n<N;n++){
a[n]=mul(add(dp[n],1),mul(I[n],now));
now=mul(now,m-1);
}
mul(a,b,c);
int in=inv(m);
now=1;
for(int n=0;n<N;n++){
dp[n]=mul(c[n],mul(F[n],now));
//if(n!=0)printf("%i ",dp[n]);
now=mul(now,in);
}
//printf("\n");
for(auto qu:Qs[m]){
ans[qu.second]=dp[qu.first];
}
}
}
int main(){
int t;
scanf("%i",&t);
for(int i=1;i<=t;i++){
int n,m;
scanf("%i %i",&n,&m);
Qs[m].pb({n,i});
}
Solve();
for(int i=1;i<=t;i++)printf("%i\n",ans[i]);
return 0;
}
詳細信息
Test #1:
score: 0
Memory Limit Exceeded
input:
4 3 2 1 1 20 23 8000 8000