QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#431806#8715. 放苹果A_zjzjAC ✓248ms26248kbC++143.6kb2024-06-06 07:05:412024-06-06 07:05:42

Judging History

This is the latest submission verdict.

  • [2024-06-06 07:05:42]
  • Judged
  • Verdict: AC
  • Time: 248ms
  • Memory: 26248kb
  • [2024-06-06 07:05:41]
  • Submitted

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,我给组数据试试?

详细

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