QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396679#6736. Alice and BobfangzAC ✓117ms237716kbC++142.0kb2024-04-23 01:04:082024-04-23 01:04:08

Judging History

你现在查看的是最新测评结果

  • [2024-04-23 01:04:08]
  • 评测
  • 测评结果:AC
  • 用时:117ms
  • 内存:237716kb
  • [2024-04-23 01:04:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define int long long
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 1e07+10;
const LL mod = 998244353;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}
LL qpow(LL a , LL b)//快速幂
{
	LL sum=1;
	while(b){
		if(b&1){
			sum=sum*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return sum;
}
LL f[N] , g[N];
void init(){
	f[0] = g[0] = 1;
	for(int i=1;i < N; i ++){
    	f[i]= f[i-1] * i % mod; //计算i的阶乘
	}
	g[N - 1] = qpow(f[N - 1] , mod - 2);
	for(int i = N - 1 ; i >= 1 ; i --){
		g[i - 1] = g[i] * i % mod;
	}
}
LL get(int n,int m){ //得到C(n,m)的组合数答案
	if(n < m)
		return 0;
	else
    	return f[n] * g[m] % mod * g[n-m] % mod;
}
LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
void solve() 
{
	//起步是1 Alice必输
	//若Alice能够将比他小的移到第一个,那么Alice赢,否则Alice输
	//
	cin >> n;
	LL ans = f[n - 1];//1开头必输
	for(int i = 2 ; i <= n ; i ++){
		//1在外面
		//共有i - 1个数
		int res = n - i;
		//从res个数里面选i - 1个数组成排列 -> c(res , i - 1) * f[i - 1] = f[res]
		if(i - 1 > res){
			break;
		}
		//[res - 2 , res - 2]
		//[res - 4 , res - 3]
		//[res - 6 , res - 4]
		int add = f[n - i] * g[n - i - i + 1];
		add %= mod;
		add *= f[n - i];
		add %= mod;
		ans += add;
	//	cout << add << endl;
		ans %= mod;
	}
	cout << ans;
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
    init();
//	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 79ms
memory: 237604kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 79ms
memory: 237488kb

input:

2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 95ms
memory: 237488kb

input:

10

output:

997920

result:

ok 1 number(s): "997920"

Test #4:

score: 0
Accepted
time: 93ms
memory: 237648kb

input:

100

output:

188898954

result:

ok 1 number(s): "188898954"

Test #5:

score: 0
Accepted
time: 80ms
memory: 237484kb

input:

4

output:

10

result:

ok 1 number(s): "10"

Test #6:

score: 0
Accepted
time: 79ms
memory: 237712kb

input:

8

output:

12336

result:

ok 1 number(s): "12336"

Test #7:

score: 0
Accepted
time: 87ms
memory: 237508kb

input:

16

output:

373118483

result:

ok 1 number(s): "373118483"

Test #8:

score: 0
Accepted
time: 91ms
memory: 237364kb

input:

32

output:

314585464

result:

ok 1 number(s): "314585464"

Test #9:

score: 0
Accepted
time: 95ms
memory: 237700kb

input:

64

output:

627827331

result:

ok 1 number(s): "627827331"

Test #10:

score: 0
Accepted
time: 95ms
memory: 237644kb

input:

128

output:

828497685

result:

ok 1 number(s): "828497685"

Test #11:

score: 0
Accepted
time: 101ms
memory: 237452kb

input:

256

output:

65697890

result:

ok 1 number(s): "65697890"

Test #12:

score: 0
Accepted
time: 87ms
memory: 237448kb

input:

512

output:

854187619

result:

ok 1 number(s): "854187619"

Test #13:

score: 0
Accepted
time: 67ms
memory: 237716kb

input:

1024

output:

513823539

result:

ok 1 number(s): "513823539"

Test #14:

score: 0
Accepted
time: 88ms
memory: 237368kb

input:

1361956

output:

617368199

result:

ok 1 number(s): "617368199"

Test #15:

score: 0
Accepted
time: 107ms
memory: 237540kb

input:

7579013

output:

827172636

result:

ok 1 number(s): "827172636"

Test #16:

score: 0
Accepted
time: 103ms
memory: 237580kb

input:

8145517

output:

710624331

result:

ok 1 number(s): "710624331"

Test #17:

score: 0
Accepted
time: 101ms
memory: 237656kb

input:

6140463

output:

707600568

result:

ok 1 number(s): "707600568"

Test #18:

score: 0
Accepted
time: 91ms
memory: 237396kb

input:

3515281

output:

698302413

result:

ok 1 number(s): "698302413"

Test #19:

score: 0
Accepted
time: 97ms
memory: 237584kb

input:

6969586

output:

69470392

result:

ok 1 number(s): "69470392"

Test #20:

score: 0
Accepted
time: 82ms
memory: 237604kb

input:

2888636

output:

433579983

result:

ok 1 number(s): "433579983"

Test #21:

score: 0
Accepted
time: 103ms
memory: 237616kb

input:

9999998

output:

758172780

result:

ok 1 number(s): "758172780"

Test #22:

score: 0
Accepted
time: 117ms
memory: 237460kb

input:

9999999

output:

605195495

result:

ok 1 number(s): "605195495"

Test #23:

score: 0
Accepted
time: 108ms
memory: 237564kb

input:

10000000

output:

866813682

result:

ok 1 number(s): "866813682"