原题传送门
思路
这道题怎么说呢，一眼题，就是让你求没有超过辰辰得票数的数量的排列组合，需要用到组合数学知识，但一看数据范围，我去 \(n\le 1e6\)，暴力的思路瞬间消失掉了就需要考虑算法了。
做法
求组合数 \(C(n,n{\div} 2)\) 的时候需要用到 \(Lucas\) 定理，通过卢卡斯定理来求较大数的组合数，正好可以通过这道题。
于是就愉快的解决了。
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 10;
const ll INF = 1e18, p = 998244353;
ll fpm(ll a, ll b)
{
ll res = a % p, ans = 1;
while (b)
{
if (b & 1)
{
ans *= res;
ans %= p;
}
res *= res;
res %= p;
b >>= 1;
}
return ans % p;
}
ll C(ll n, ll m)
{
if (m > n)
return 0;
ll ret = 1;
m = min(n - m, m);
for (int i = 1; i <= m; i++)
{
ll a = (n + i - m) % p;
ll b = i % p;
ret = ret * (a * fpm(b, p - 2) % p) % p;
}
return ret;
}
ll lca(ll n, ll m)
{
if (m == 0)
return 1;
return C(n % p, m % p) * lca(n / p, m / p) % p;
}
int main()
{ // freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
scanf("%d", &n);
int m = n / 2;
printf("%lld\n", lca(n, m));
return 0;
}