[UOJ#275]【清华集训2016】组合数问题
试题描述
组合数 (C_n^m) 表示的是从 (n) 个物品中选出 (m) 个物品的方案数。举个例子，从 ((1,2,3)) 三个物品中选择两个物品可以有 ((1,2),(1,3),(2,3)) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 (C_n^m) 的一般公式：
egin{equation}
C_n^m=frac{n!}{m!(n−m)!}
otag
end{equation}
其中 (n!=1 imes 2 imes cdots imes n)。（额外的，当 (n=0) 时， (n!=1)）
小葱想知道如果给定 (n,m) 和 (k)，对于所有的 (0 le i le n,0 le j le min(i,m)) 有多少对 ((i,j)) 满足 (C_i^j) 是 (k) 的倍数。
答案对 (10^9+7) 取模。
输入
第一行有两个整数 (t,k)，其中 (t) 代表该测试点总共有多少组测试数据。
接下来 (t) 行每行两个整数 (n,m)。
输出
(t) 行，每行一个整数代表所有的 (0 le i le n,0 le j le min(i,m)) 中有多少对 ((i,j)) 满足 (C_i^j) 是 (k) 的倍数。
输入示例1
1 2
3 3
输出示例1
1
输入示例2
2 5
4 5
6 7
输出示例2
0
7
输入示例3
3 23
23333333 23333333
233333333 233333333
2333333333 2333333333
输出示例3
851883128
959557926
680723120
数据规模及约定
对于 (20 exttt{%}) 的测试点，(1 le n,m le 100)；
对于另外 (15 exttt{%}) 的测试点，(n le m)；
对于另外 (15 exttt{%}) 的测试点，(k=2)；
对于另外 (15 exttt{%}) 的测试点， (m le 10)；
对于 (100 exttt{%}) 的测试点， (1 le n,m le 10^{18},1 le t,k le 100)，且 (k) 是一个质数。
题解
千万不要忘了 (k) 是一个质数！！！
这题用 Lucas 定理，即 (C_n^m mod p = C_{n mod p}^{m mod p} cdot C_{lfloorfrac{n}{p} floor}^{lfloorfrac{m}{p} floor} mod p)，那么就不难想到把 (n) 和 (m) 变成 (k) 进制数然后数位 dp 了。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define LL long long
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (t); i >= (s); i--)
LL read() {
LL x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 61
#define maxk 102
#define MOD 1000000007
int T, K, C[maxk][maxk];
struct Num {
LL val;
int num[maxn], cntn;
Num() {}
Num(LL _): val(_) {
memset(num, 0, sizeof(num));
cntn = 0;
LL x = val;
while(x) num[cntn++] = x % K, x /= K;
// for(int i = 0; i < (cntn >> 1); i++) swap(num[i], num[cntn-i-1]);
}
} N, M;
int f[maxn][2][2][2][2];
void add(int& a, int b) {
a += b;
if(a >= MOD) a -= MOD;
return ;
}
void dp() {
/* _a: whether a equals N.val right now
* _b: whether b equals M.val right now
* _lab: whether a equals b before
* _zero: whether the result(mod K) is already zero
*/
rep(n, 0, N.cntn - 1)
rep(_a, 0, 1) rep(_b, 0, 1) rep(_ab, 0, 1) rep(_zero, 0, 1)
rep(a, 0, _a ? N.num[n] : K - 1) rep(b, 0, min(_b ? M.num[n] : K - 1, _ab ? a : K - 1))
if(!n) add(f[n][_a][_b][_ab][_zero], _zero | !C[a][b]);
else add(f[n][_a][_b][_ab][_zero], f[n-1][_a&a==N.num[n]][_b&b==M.num[n]][_ab&a==b][_zero|!C[a][b]]);
return ;
}
int main() {
T = read(); K = read();
for(int i = 0; i < K; i++) {
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; j++) {
C[i][j] = C[i-1][j-1] + C[i-1][j];
if(C[i][j] >= K) C[i][j] -= K;
}
}
while(T--) {
N = Num(read());
M = Num(min(read(), N.val));
memset(f, 0, sizeof(f));
dp();
printf("%d
", f[N.cntn-1][1][1][1][0]);
}
return 0;
}