洛谷 P4345 [SHOI2015]超能粒子炮·改（卢卡斯定理）

超能粒子炮·改（卢卡斯定理）"/>

洛谷 P4345 [SHOI2015]超能粒子炮·改（卢卡斯定理）

1、设 f[n][k] = c(n, 0) + c(n, 1) + … + c(n, k)
递归公式看其他老哥推导的
递推公式 f(n, k) = f(n / p, k / p - 1) * f(n % p, p - 1)
+ f(n % p, k % p) * c(k / p, n / p)
2、当 n <= p 时候，用递推法初始化 组合数 的数组
c(n, k) = c(n - 1, k) + c(n - 1, k - 1)

3、当 n <= p 时候， 计算f(n, k)， 一定算完整 ，从 f[0][0] 到 f[p][p]
4、当 n > p 时候，组合数，用卢卡斯定理算。
卢卡斯 lucas 函数写个递归算， 递推公式f(n, k) 也写个递归算

#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long ll;
const int p = 2333;
const ll maxn = 2335;
ll f[maxn + 2][maxn + 2];	// 组合数前缀和 f[i][j] = c[i][0] + c[i][1] + ... + c[i][j]
ll c[maxn + 2][maxn + 2];	//组合数
ll T, N, K;ll lucas(ll n, ll m)
{