QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#877796#6736. Alice and Bobnullptr_qwqAC ✓140ms121100kbC++172.1kb2025-02-01 08:46:572025-02-01 08:46:57

Judging History

This is the latest submission verdict.

  • [2025-02-01 08:46:57]
  • Judged
  • Verdict: AC
  • Time: 140ms
  • Memory: 121100kb
  • [2025-02-01 08:46:57]
  • Submitted

answer


#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
using namespace std;
ll read(){
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=10000005;
inline int qpow(int x,ll y){
	int rt=1;
	for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) rt=1ll*rt*x%mod;
	return rt;
}
inline void inc(int &x,const int y){ x=(x+y>=mod)?(x+y-mod):(x+y); }
inline void dec(int &x,const int y){ x=(x>=y)?(x-y):(x+mod-y); }
inline void mul(int &x,const int y){ x=1ll*x*y%mod; }
inline int add(const int x,const int y){ return (x+y>=mod)?(x+y-mod):(x+y); }
inline int sub(const int x,const int y){ return (x>=y)?(x-y):(x+mod-y); }
inline int prod(const int x,const int y){ return 1ll*x*y%mod; }
namespace combi{
	int fac[maxn],ifac[maxn],inv[maxn];
	void init(const int N){
		fac[0]=ifac[0]=inv[0]=1;
		F(i,1,N) fac[i]=1ll*fac[i-1]*i%mod;
		ifac[N]=qpow(fac[N],mod-2);
		dF(i,N-1,1) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
		F(i,1,N) inv[i]=1ll*ifac[i]*fac[i-1]%mod;
	}
	inline int C(const int n,const int m){
		if(m>n||n<0||m<0) return 0;
		return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
	}
}
using namespace combi;
int n;
void solve(){
	n=read(),init(n);
	int ans=0;
	F(i,1,n)inc(ans,1ll*C(n-i,i-1)*fac[i-1]%mod*fac[n-i]%mod);
	printf("%d",ans);
}
signed main(){
	const int zsy=1;
	F(____,1,zsy)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 8008kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 8012kb

input:

2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 0ms
memory: 7884kb

input:

10

output:

997920

result:

ok 1 number(s): "997920"

Test #4:

score: 0
Accepted
time: 0ms
memory: 8008kb

input:

100

output:

188898954

result:

ok 1 number(s): "188898954"

Test #5:

score: 0
Accepted
time: 1ms
memory: 8012kb

input:

4

output:

10

result:

ok 1 number(s): "10"

Test #6:

score: 0
Accepted
time: 0ms
memory: 7880kb

input:

8

output:

12336

result:

ok 1 number(s): "12336"

Test #7:

score: 0
Accepted
time: 1ms
memory: 8008kb

input:

16

output:

373118483

result:

ok 1 number(s): "373118483"

Test #8:

score: 0
Accepted
time: 0ms
memory: 8008kb

input:

32

output:

314585464

result:

ok 1 number(s): "314585464"

Test #9:

score: 0
Accepted
time: 0ms
memory: 8008kb

input:

64

output:

627827331

result:

ok 1 number(s): "627827331"

Test #10:

score: 0
Accepted
time: 0ms
memory: 7968kb

input:

128

output:

828497685

result:

ok 1 number(s): "828497685"

Test #11:

score: 0
Accepted
time: 0ms
memory: 8012kb

input:

256

output:

65697890

result:

ok 1 number(s): "65697890"

Test #12:

score: 0
Accepted
time: 0ms
memory: 8004kb

input:

512

output:

854187619

result:

ok 1 number(s): "854187619"

Test #13:

score: 0
Accepted
time: 0ms
memory: 7884kb

input:

1024

output:

513823539

result:

ok 1 number(s): "513823539"

Test #14:

score: 0
Accepted
time: 19ms
memory: 22052kb

input:

1361956

output:

617368199

result:

ok 1 number(s): "617368199"

Test #15:

score: 0
Accepted
time: 106ms
memory: 95684kb

input:

7579013

output:

827172636

result:

ok 1 number(s): "827172636"

Test #16:

score: 0
Accepted
time: 112ms
memory: 106656kb

input:

8145517

output:

710624331

result:

ok 1 number(s): "710624331"

Test #17:

score: 0
Accepted
time: 84ms
memory: 82992kb

input:

6140463

output:

707600568

result:

ok 1 number(s): "707600568"

Test #18:

score: 0
Accepted
time: 45ms
memory: 51524kb

input:

3515281

output:

698302413

result:

ok 1 number(s): "698302413"

Test #19:

score: 0
Accepted
time: 96ms
memory: 89900kb

input:

6969586

output:

69470392

result:

ok 1 number(s): "69470392"

Test #20:

score: 0
Accepted
time: 39ms
memory: 45104kb

input:

2888636

output:

433579983

result:

ok 1 number(s): "433579983"

Test #21:

score: 0
Accepted
time: 140ms
memory: 121100kb

input:

9999998

output:

758172780

result:

ok 1 number(s): "758172780"

Test #22:

score: 0
Accepted
time: 139ms
memory: 120896kb

input:

9999999

output:

605195495

result:

ok 1 number(s): "605195495"

Test #23:

score: 0
Accepted
time: 138ms
memory: 120968kb

input:

10000000

output:

866813682

result:

ok 1 number(s): "866813682"