QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396678#6736. Alice and BobfangzTL 68ms159372kbC++141.9kb2024-04-23 00:51:592024-04-23 00:52:00

Judging History

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

  • [2024-04-23 00:52:00]
  • 评测
  • 测评结果:TL
  • 用时:68ms
  • 内存:159372kb
  • [2024-04-23 00:51:59]
  • 提交

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的阶乘
	}
}
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 l = n - i - i + 2 , r = n - i;
		int add = 1;
		for(int j = l ; j <= r ; j ++){
			add *= j;
			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: 52ms
memory: 159372kb

input:

1

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 68ms
memory: 159372kb

input:

2

output:

1

result:

ok 1 number(s): "1"

Test #3:

score: 0
Accepted
time: 51ms
memory: 159356kb

input:

10

output:

997920

result:

ok 1 number(s): "997920"

Test #4:

score: 0
Accepted
time: 63ms
memory: 159360kb

input:

100

output:

188898954

result:

ok 1 number(s): "188898954"

Test #5:

score: 0
Accepted
time: 35ms
memory: 159328kb

input:

4

output:

10

result:

ok 1 number(s): "10"

Test #6:

score: 0
Accepted
time: 47ms
memory: 159360kb

input:

8

output:

12336

result:

ok 1 number(s): "12336"

Test #7:

score: 0
Accepted
time: 36ms
memory: 159272kb

input:

16

output:

373118483

result:

ok 1 number(s): "373118483"

Test #8:

score: 0
Accepted
time: 55ms
memory: 159308kb

input:

32

output:

314585464

result:

ok 1 number(s): "314585464"

Test #9:

score: 0
Accepted
time: 20ms
memory: 159280kb

input:

64

output:

627827331

result:

ok 1 number(s): "627827331"

Test #10:

score: 0
Accepted
time: 50ms
memory: 159300kb

input:

128

output:

828497685

result:

ok 1 number(s): "828497685"

Test #11:

score: 0
Accepted
time: 43ms
memory: 159272kb

input:

256

output:

65697890

result:

ok 1 number(s): "65697890"

Test #12:

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

input:

512

output:

854187619

result:

ok 1 number(s): "854187619"

Test #13:

score: 0
Accepted
time: 44ms
memory: 159256kb

input:

1024

output:

513823539

result:

ok 1 number(s): "513823539"

Test #14:

score: -100
Time Limit Exceeded

input:

1361956

output:


result: