原题传送门
思路
这道题怎么说呢,一眼题,就是让你求没有超过辰辰得票数的数量的排列组合,需要用到组合数学知识,但一看数据范围,我去 \(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;
}
标签:GCC,res,ll,竞选,pragma,ans,班长,optimize
From: https://www.cnblogs.com/gongyuchen/p/17804764.html