快速幂 + 高精度 + 分解质因子法求组合数
学了知识一定要勤于复习呀
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1010, mod = 1000;
int k, x;
int primes[N], cnt;
int sum[N];
bool st[N];
int qmi(int x, int k)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * x % mod;
x = (LL)x * x % mod;
k >>= 1;
}
return res;
}
void get_primes(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 a, int p)
{
int res = 0;
while (a)
{
res += a / p;
a /= p;
}
return res;
}
vector<int> mul(vector<int> A, int b)
{
vector<int> res;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
res.push_back(t % 10);
t /= 10;
}
return res;
}
int main()
{
cin >> k >> x;
int g = qmi(x, x);
get_primes(g);
for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
sum[i] = get(g - 1, p) - get(k - 1, p) - get(g - k, p);
}
vector<int> C;
C.push_back(1);
for (int i = 0; i <= cnt; i ++ )
for (int j = 0; j < sum[i]; j ++ )
C = mul(C, primes[i]);
for (int i = C.size() - 1; ~i; i --) cout << C[i];
return 0;
}