模板
a,b ⇐ 2000
如果每次都根据定义式算阶乘, 会超时, 可以提前预处理出来。 根据这个可以类似dp的方式求出来
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e3 + 10, MOD = 1e9 + 7;
int f[N][N];
void pre()
{
for(int i = 0; i < N; i++)
for(int j = 0; j <= i; j++)
{
if(!j) f[i][j] = 1;
else f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % MOD;
}
}
int main()
{
pre();
int n;
cin >> n;
while(n--)
{
int a,b;
cin >> a >> b;
cout << f[a][b] << endl;
}
return 0;
}a,b ⇐ 1e5
不能再直接算所有C, 可以通过预处理所有阶乘：
a! 就直接 fact[i - 1] * i
分母则是逆元＋费马定理：
infact[i - 1] * qmi(i, MOD - 2, MOD)
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, MOD = 1e9 + 7;
int fact[N], infact[N];
int n;
int qmi(int a, int b, int p)
{
int res = 1;
while(b)
{
if(b & 1) res = (LL)res * a % p;
b >>= 1;
a = (LL)a* a % p;
}
return res ;
}
int main()
{
fact[0] = infact[0] = 1;
for(int i = 1; i <= N; i++)
{
fact[i] = (LL)fact[i - 1] * i % MOD;
infact[i] = (LL)infact[i - 1]*qmi(i, MOD - 2, MOD) % MOD;
}
cin >> n;
while(n--)
{
int a, b;
cin >> a >> b;
cout << (LL)fact[a] * infact[b] % MOD * infact[a - b] % MOD << endl;
}
return 0;
}a,b ⇐ 1e18
卢卡斯定理 Lucas 算 后面一个式子时也这样递归的计算, 直到最后p > a,b
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL p;
int qmi(LL a, LL b ,LL p)
{
int res = 1;
while(b)
{
if(b & 1) res = (LL) res * a % p;
b >>= 1;
a = (LL) a * a % p;
}
return res;
}
int C(LL a, LL b)
{
int res = 1;
for(int i = 1, j = a; i <= b; i++, j--)
{
res = (LL) res * j % p;
res = (LL) res * qmi(i, p - 2, p) % p;
}
return res;
}
int lucas(LL a, LL b)
{
if(a < p && b < p) return C(a,b);
return (LL) C(a%p, b%p)*lucas(a/p, b/p) % p;
}
int main()
{
int n;
cin >> n;
while (n -- ){
LL a, b;
cin >> a >> b >> p;
cout << lucas(a,b) << endl;
}
return 0;
}a,b ⇐ 5000 无mod
需要用到高精度, 直接根据定义来算： 可以利用分解质因数的原理, 来将除法省去。 阶乘的分解质因数为：
// 求n!中质因子p的个数
int get(int n,int p)
{
int res = 0;
while(n)
{
res += n / p;
n /= p;
}
return res;
}然后该式子可以表示为： 即为原式包含 质因子 p 的个数
最后把所有的质因子乘起来即可：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 5e3 + 10;
int primes[N], cnt;
bool st[N];
int sum[N];
void getprimes(int n)
{
for(int i = 2; i <= n;i ++)
{
if(!st[i]) primes[cnt++] = i;
for(int j = 0; primes[j] <= n / i; j++)
{
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
int get(int n,int p)
{
int res = 0;
while(n)
{
res += n / p;
n /= p;
}
return res;
}
vector<int> mul(vector<int> res, int x)
{
vector<int> c;
int t = 0;
for(int i = 0; i < res.size(); i++)
{
t += res[i] * x;
c.push_back(t % 10);
t /= 10;
}
while(t)
{
c.push_back(t % 10);
t/=10;
}
return c;
}
int main()
{
int a,b;
cin >> a >> b;
getprimes(a);
for(int i = 0; i < cnt; i++)
{
int p = primes[i];
sum[i] = get(a,p) - get(b,p) - get(a - b,p);
}
vector<int> res;
res.push_back(1);
for(int i = 0; i < cnt; i++)
for(int j = 1; j <= sum[i]; j++)
res = mul(res, primes[i]);
for(int i = res.size() - 1; i >= 0; i--)
{
cout << res[i];
}
return 0;
}卡特兰数
title: 题目
给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
输出的答案对 10^9+7 取模。
title: input
3title: output
5title: 思路
进行二维建模, 从 (0,0)出发, 1为向上(y), 0为向右(x)。
那么平面上每个点就是一个前缀序列, 终点 p(x,y) 的坐标就是 0,1 的个数, 所有满足 x>=y 的点数量就是最后结果。
超过黄线,即经过蓝线的解不符合条件, 故总答案为：
总数量很好计算 , 共走12步, 6步向右, 剩下六步向左的所有方案。
经过蓝线的数量不好计算, 做个变换将其区分出来, 这里把经过蓝色先的路径做一个对称：
可以得出, 所有经过蓝色线到达(6,6)的路径, 在对于蓝线做对称后到达的点一定是 (5,7), 即
所以结果为：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int p = 1e9 + 7;
int qmi(int a, int b, int p)
{
int res = 1;
while(b)
{
if(b & 1) res = (LL) res * a % p;
b >>= 1;
a = (LL) a * a % p;
}
return res;
}
int main()
{
int n,res = 1;
cin >> n;
int a = 2*n, b = n;
for(int i = a; i > a-b; i--) res = (LL) res * i % p;
for(int i = 1; i <= b; i++) res = (LL) res * qmi(i, p - 2, p) % p;
res = (LL) res * qmi(n + 1, p - 2, p) % p;
cout << res << endl;
return 0;
}