QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#396683#6736. Alice and BobfangzTL 0ms0kbC++142.0kb2024-04-23 01:07:202024-04-23 01:07:21

Judging History

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

  • [2024-04-23 01:07:21]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-04-23 01:07:20]
  • 提交

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[i] = g[i-1] * qpow(i , mod - 2) % mod; //计算i的乘法逆元 qpow为快速幂
	}
}
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: 0
Time Limit Exceeded

input:

1

output:


result: