QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#447555 | #8715. 放苹果 | 275307894a | AC ✓ | 254ms | 45116kb | C++14 | 5.6kb | 2024-06-18 16:18:43 | 2024-06-18 16:18:45 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=2e5+5,M=N*4+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
using poly=vector<ll>;
ll mpow(ll x,int y=mod-2){ll ans=1;while(y) y&1&&(ans=ans*x%mod),y>>=1,x=x*x%mod;return ans;}
ll sgn(int x){return x&1?mod-1:1;}
namespace Poly{
const int N=1<<21,g=3;
int tr[N],k,a[N],b[N];ll pw[N];
void init(int n){
for(k=2;k<=n;k<<=1);
for(int i=0;i<k;i++) tr[i]=(tr[i>>1]>>1)|(i&1?k/2:0);
pw[k/2]=1;pw[k/2+1]=mpow(g,(mod-1)/k);
for(int i=k/2+2;i<k;i++) pw[i]=pw[i-1]*pw[k/2+1]%mod;
for(int i=k/2-1;i;i--) pw[i]=pw[i<<1];
}
void ntt(int *A,int k,int flag){
static ull a[N];for(int i=0;i<k;i++) a[tr[i]]=A[i];
for(int i=2;i<=k;i<<=1){
ll *e=pw+i/2;
for(int j=0;j<k;j+=i){
for(int h=j;h<j+i/2;h++){
int x=a[h+i/2]*e[h-j]%mod;
a[h+i/2]=a[h]+mod-x;a[h]+=x;
}
}
if(i==(1<<18)){
for(int j=0;j<k;j++) a[j]%=mod;
}
}
for(int i=0;i<k;i++) A[i]=a[i]%mod;
if(flag) return;
reverse(A+1,A+k);
ll iv=mpow(k);for(int i=0;i<k;i++) A[i]=A[i]*iv%mod;
}
namespace Public{
poly operator *(const poly &A,const poly &B){
int n=A.size(),m=B.size(),lim=n+m-1;
init(lim);
copy(A.begin(),A.end(),a);fill(a+n,a+k,0);
copy(B.begin(),B.end(),b);fill(b+m,b+k,0);
ntt(a,k,1);ntt(b,k,1);
for(int i=0;i<k;i++) a[i]=1ll*a[i]*b[i]%mod;
ntt(a,k,0);
poly c(lim);copy(a,a+lim,c.begin());
return c;
}
poly& operator *=(poly &A,const poly &B){
return A=A*B;
}
poly operator *(const poly &A,const int B){
poly C=A;for(int i=0;i<C.size();i++) C[i]=1ll*C[i]*B%mod;
return C;
}
poly& operator *=(poly &A,const int &B){
return A=A*B;
}
poly operator +(const poly &A,const poly &B){
poly C(max(A.size(),B.size()));
for(int i=0;i<A.size();i++) C[i]=A[i];
for(int i=0;i<B.size();i++) C[i]=(B[i]+C[i])%mod;
return C;
}
poly& operator +=(poly &A,const poly &B){
return A=A+B;
}
poly operator -(const poly &A,const poly &B){
poly C(max(A.size(),B.size()));
for(int i=0;i<A.size();i++) C[i]=A[i];
for(int i=0;i<B.size();i++) C[i]=(C[i]+mod-B[i])%mod;
return C;
}
poly& operator -=(poly &A,const poly &B){
return A=A-B;
}
poly operator %(const poly &A,const int &B){
poly C=A;
if(C.size()>B) C.resize(B);
return C;
}
poly& operator %=(poly &A,const int B){
return A=A%B;
}
poly inve(poly A,int n=-1){
if(n==-1) n=A.size();
if(n==1) return poly({(int)mpow(A[0])});
poly A0=inve(A%(n+1>>1),n+1>>1);
return A0*(poly({2})-A*A0%n)%n;
}
poly sqrt(poly A,int n=-1){
if(n==-1) n=A.size();
if(n==1) return poly({1});
poly A0=sqrt(A%(n+1>>1),n+1>>1);
return (A0*A0%n+A)*inve(A0,n)%n*(mod+1>>1);
}
poly der(poly A){
poly B(A.size()-1);
for(int i=1;i<A.size();i++) B[i-1]=1ll*A[i]*i%mod;
return B;
}
poly integ(poly A){
poly B(A.size()+1);
static ll inv[N];inv[1]=1;for(int i=2;i<=A.size();i++) inv[i]=(mod-inv[mod%i])*(mod/i)%mod;
for(int i=0;i<A.size();i++) B[i+1]=inv[i+1]*A[i]%mod;
return B;
}
poly ln(poly A,int n=-1){
if(n==-1) n=A.size();
return integ(der(A)*inve(A,n)%n)%n;
}
poly exp(poly A,int n=-1){
if(n==-1) n=A.size();
if(n==1) return poly({1});
poly A0=exp(A%(n+1>>1),n+1>>1);
return A0*(poly({1})-ln(A0,n)+A)%n;
}
poly mpow(poly A,int n,ll k){gdb(n,k);
auto p=find_if(A.begin(),A.end(),[](ll x){return x;})-A.begin();
if(p==A.size()) return A;
poly B(A.size()-p);for(int i=p;i<A.size();i++) B[i-p]=A[i];
ll v=::mpow(B[0],k%Mod),iv=::mpow(B[0]);
for(ll &i:B) i=i*iv%mod;B=ln(B,n);
for(ll &i:B) i=k%mod*i%mod;B=exp(B,n);
for(ll &i:B) i=i*v%mod;
for(int i=n-1;~i;i--) B[i]=(i>=1ll*k*p?B[i-k*p]:0);
return B;
}
}
}using namespace Poly::Public;
int n,m;ll frc[N],inv[N];
ll C(int x,int y){return frc[x]*inv[y]%mod*inv[x-y]%mod;}
void Solve(){
int i,j;scanf("%d%d",&n,&m);
inv[1]=1;for(i=2;i<=n+1;i++) inv[i]=(mod-inv[mod%i])*(mod/i)%mod;
for(frc[0]=inv[0]=i=1;i<=n+1;i++) inv[i]=inv[i-1]*inv[i]%mod,frc[i]=frc[i-1]*i%mod;
poly g(n+1),f(n+1);
for(i=0;i<=n;i++) f[i]=inv[n-i];
for(i=0;i<=n;i++) g[n-i]=frc[n-i]*C(n,i)%mod*min(i,n-i)%mod*sgn(i)%mod;
g*=f;
poly val(g.begin()+n,g.begin()+2*n+1);
for(i=0;i<=n;i++) val[i]=val[i]*mpow(m,i)%mod*sgn(n-i)%mod*inv[i]%mod;
reverse(all(val));
poly pws(n+1),iv(n+1);
for(i=0;i<=n;i++) pws[i]=mpow(m+1,i+1)*inv[i+1]%mod;
for(i=0;i<=n;i++) iv[i]=inv[i+1];
pws*=inve(iv);
ll ans=0;
for(i=0;i<=n;i++){
gdb(pws[i]*frc[i]%mod);
(ans+=pws[i]*frc[i]%mod*val[i])%=mod;
}
printf("%lld\n",ans%mod);
}
int main(){
int t=1;
// scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 4176kb
input:
2 3
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 1ms
memory: 4176kb
input:
3 3
output:
36
result:
ok 1 number(s): "36"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3996kb
input:
1 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4024kb
input:
1 2
output:
0
result:
ok 1 number(s): "0"
Test #5:
score: 0
Accepted
time: 1ms
memory: 4044kb
input:
1 3
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 1ms
memory: 4012kb
input:
2 1
output:
0
result:
ok 1 number(s): "0"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4016kb
input:
3 1
output:
0
result:
ok 1 number(s): "0"
Test #8:
score: 0
Accepted
time: 3ms
memory: 4728kb
input:
3719 101
output:
78994090
result:
ok 1 number(s): "78994090"
Test #9:
score: 0
Accepted
time: 2ms
memory: 4696kb
input:
2189 1022
output:
149789741
result:
ok 1 number(s): "149789741"
Test #10:
score: 0
Accepted
time: 3ms
memory: 4576kb
input:
2910 382012013
output:
926541722
result:
ok 1 number(s): "926541722"
Test #11:
score: 0
Accepted
time: 155ms
memory: 36348kb
input:
131072 3837829
output:
487765455
result:
ok 1 number(s): "487765455"
Test #12:
score: 0
Accepted
time: 237ms
memory: 42880kb
input:
183092 100000000
output:
231786691
result:
ok 1 number(s): "231786691"
Test #13:
score: 0
Accepted
time: 233ms
memory: 44708kb
input:
197291 937201572
output:
337054675
result:
ok 1 number(s): "337054675"
Test #14:
score: 0
Accepted
time: 230ms
memory: 45112kb
input:
200000 328194672
output:
420979346
result:
ok 1 number(s): "420979346"
Test #15:
score: 0
Accepted
time: 254ms
memory: 45116kb
input:
200000 1000000000
output:
961552572
result:
ok 1 number(s): "961552572"
Extra Test:
score: 0
Extra Test Passed