QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431806 | #8715. 放苹果 | A_zjzj | AC ✓ | 248ms | 26248kb | C++14 | 3.6kb | 2024-06-06 07:05:41 | 2024-06-06 07:05:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned ll;
const int N=2e5+10,mod=998244353;
int n,m;
ll qpow(ll x,ll y=mod-2,ll ans=1){
for(;y;(x*=x)%=mod,y>>=1)if(y&1)(ans*=x)%=mod;
return ans;
}
int fac[N],ifac[N];
int C(int n,int m){
if(0>m||m>n)return 0;
return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void init(int n){
for(int i=fac[0]=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
ifac[n]=qpow(fac[n]);
for(int i=n;i>=1;i--)ifac[i-1]=1ll*ifac[i]*i%mod;
}
namespace Poly{
const int N=1<<19,g=3;
int lim,rev[N],A[N],B[N],pw[N];
void init(int n){
for(lim=1;lim<n;lim<<=1);
for(int i=1;i<lim;i++)rev[i]=rev[i>>1]>>1|(i&1?lim>>1:0);
}
void Init(){
int x=qpow(g,(mod-1)/N);
pw[N/2]=1;
for(int i=N/2+1;i<N;i++)pw[i]=1ll*pw[i-1]*x%mod;
for(int i=N/2-1;i;i--)pw[i]=pw[i<<1];
}
namespace Public{
using poly=vector<int>;
void NTT(int *f,int op){
static unsigned long long a[N];
for(int i=0;i<lim;i++)a[i]=f[rev[i]];
for(int len=1,x;len<lim;len<<=1){
for(int i=0;i<lim;i+=len<<1){
for(int j=0;j<len;j++){
x=a[i|j|len]*pw[len|j]%mod;
a[i|j|len]=a[i|j]+mod-x,a[i|j]+=x;
}
}
if(len>>16&1){
for(int i=0;i<lim;i++)a[i]%=mod;
}
}
for(int i=0;i<lim;i++)f[i]=a[i]%mod;
if(op<0){
reverse(f+1,f+lim);
int x=qpow(lim);
for(int i=0;i<lim;i++)f[i]=1ll*f[i]*x%mod;
}
}
poly operator * (const poly &a,const poly &b){
int n=a.size(),m=b.size(),k=n+m-1;
init(k);
copy(a.begin(),a.end(),A),fill(A+n,A+lim,0);
copy(b.begin(),b.end(),B),fill(B+m,B+lim,0);
poly c(k);
NTT(A,1),NTT(B,1);
for(int i=0;i<lim;i++)A[i]=1ll*A[i]*B[i]%mod;
NTT(A,-1);
for(int i=0;i<k;i++)c[i]=A[i];
return c;
}
poly& operator *= (poly &a,const poly &b){
return a=a*b;
}
poly& operator %= (poly &a,const int &b){
if(a.size()>b)a.resize(b);
return a;
}
poly operator % (const poly &a,const int &b){
poly c(a);
return c%=b;
}
poly& operator -= (poly &a,const poly &b){
int n=a.size(),m=b.size();
if(n<m)a.resize(m);
for(int i=0;i<m;i++)(a[i]+=mod-b[i])%=mod;
return a;
}
poly operator - (const poly &a,const poly &b){
poly c(a);
return c-=b;
}
poly inv(const poly &a,int k=-1){
if(!~k)k=a.size();
poly b{(int)qpow(a[0])};
for(int i=1,x;i<k;i<<=1){
x=min(i*2,k);
(b*=poly({2})-a%x*b%x)%=x;
}
return b;
}
}
}
using namespace Poly::Public;
int main(){
Poly::Init();
cin>>n>>m,init(n+1);
poly f(n+1);
for(int i=1,x=1;i<=n+1;i++){
x=1ll*x*m%mod,f[i-1]=(x-1ll)*ifac[i]%mod;
}
poly g(n+1);
for(int i=1;i<=n+1;i++)g[i-1]=ifac[i];
debug(f,g);
f=f*inv(g)%(n+1);
debug(f);
for(int i=0;i<=n;i++)f[i]=1ll*f[i]*fac[i]%mod;
reverse(all(f));
for(int i=0;i<=n;i++)f[i]=1ll*f[i]*ifac[i]%mod;
// debug(f);
// for(int i=0;i<=n;i++){
// f[i]=0;
// for(int j=1;j<m;j++){
// f[i]=(f[i]+qpow(j,n-i))%mod;
// }
// f[i]=1ll*f[i]*ifac[i]%mod;
// }
// debug(f);
for(int i=0,x=1;i<=n;i++,x=1ll*x*m%mod)f[i]=1ll*f[i]*x%mod;
poly res(f);
for(int i=0;i<=n;i++){
f[i]=1ll*(i&1?mod-1:1)*ifac[i]%mod;
}
res=res*f%(n+1);
int ans=0;
for(int i=0;i<=n;i++){
ans=(ans+1ll*min(i,n-i)*ifac[i]%mod*res[n-i])%mod;
}
ans=1ll*ans*fac[n]%mod;
cout<<ans<<endl;
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11492kb
input:
2 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 3ms
memory: 11788kb
input:
3 3
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 0ms
memory: 11540kb
input:
1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 3ms
memory: 12708kb
input:
1 2
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 3ms
memory: 11452kb
input:
1 3
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 13348kb
input:
2 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 0ms
memory: 12660kb
input:
3 1
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 5ms
memory: 12196kb
input:
3719 101
output:
78994090
result:
ok 1 number(s): "78994090"
Test #9:
score: 0
Accepted
time: 5ms
memory: 13576kb
input:
2189 1022
output:
149789741
result:
ok 1 number(s): "149789741"
Test #10:
score: 0
Accepted
time: 5ms
memory: 11776kb
input:
2910 382012013
output:
926541722
result:
ok 1 number(s): "926541722"
Test #11:
score: 0
Accepted
time: 182ms
memory: 23852kb
input:
131072 3837829
output:
487765455
result:
ok 1 number(s): "487765455"
Test #12:
score: 0
Accepted
time: 236ms
memory: 25716kb
input:
183092 100000000
output:
231786691
result:
ok 1 number(s): "231786691"
Test #13:
score: 0
Accepted
time: 242ms
memory: 26116kb
input:
197291 937201572
output:
337054675
result:
ok 1 number(s): "337054675"
Test #14:
score: 0
Accepted
time: 247ms
memory: 26092kb
input:
200000 328194672
output:
420979346
result:
ok 1 number(s): "420979346"
Test #15:
score: 0
Accepted
time: 248ms
memory: 26248kb
input:
200000 1000000000
output:
961552572
result:
ok 1 number(s): "961552572"
Extra Test:
score: 0
Extra Test Passed