洛谷P6669 组合数问题

传送门

题目描述

组合数 C_n^mC
n
m
​
表示的是从 nn 个物品中选出 mm 个物品的方案数。举个例子，从 (1,2,3)(1,2,3) 三个物品中选择两个物品可以有 (1,2),(1,3),(2,3)(1,2),(1,3),(2,3) 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 C_n^mC
n
m
​
的一般公式：

C_n^m=\dfrac{n!}{m!(n-m)!}C nm = m!(n−m)!n!

其中 n!=1×2×⋯×nn!=1×2×⋯×n。（额外的，当 n=0n=0 时，n!=1n!=1）

小葱想知道如果给定 n,mn,m 和 kk，对于所有的 0≤i≤n,0≤j≤\min(i,m)0≤i≤n,0≤j≤min(i,m) 有多少对 (i,j)(i,j) 满足 C^j_iC
i
j
​
是 kk 的倍数。

答案对 10^9+710
9
+7 取模。

输入格式

第一行有两个整数 t,kt,k，其中 tt 代表该测试点总共有多少组测试数据。

接下来 tt 行每行两个整数 n,mn,m。

输出格式
tt 行，每行一个整数代表所有的 0≤i≤n,0≤j≤\min(i,m)0≤i≤n,0≤j≤min(i,m) 中有多少对 (i,j)(i,j) 满足 C^j_iC
i
j
​
是 kk 的倍数。

输入输出样例

输入 #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

说明/提示

样例 11 解释
在所有情况中，只有 C_{2}^{1}=2C
2
1
​
=2 是 22 的倍数。

限制与约定

对于 20%20% 的测试点，1≤n,m≤1001≤n,m≤100；

对于另外 15%15% 的测试点，n≤mn≤m；

对于另外 15%15% 的测试点，k=2k=2；

对于另外 15%15% 的测试点， m\le10m≤10；

对于 100%100% 的测试点， 1≤n,m≤10^{18}1≤n,m≤10
18
，1≤t,k≤1001≤t,k≤100，且 kk 是一个质数。

上代码：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

char buf[1 << 23],*p1 = buf,*p2 = buf,obuf[1 << 23],*O = obuf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1 << 21,stdin),p1 == p2) ? EOF : *p1 ++)
#define putchar(x) *O ++ = x

template<typename T>void read(T &x) {
	x = 0;T f = 1;char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1;ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0';ch = getchar();}
	x *= f;
}
int read() {
	int x = 0, f = 1;char ch = getchar();
	while (!isdigit(ch)) {if (ch == '-') f = -1;ch = getchar();}
	while (isdigit(ch)) {x = (x << 3) + (x << 1) + ch - '0';ch = getchar();}
	return x * f;
}
template<typename T>void print(T x) {
	if (x < 0) putchar('-'),x = -x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}

template<typename T>T Abs(T x) {return x < 0 ? -x : x;}
template<typename T>T Min(T x,T y) {return x < y ? x : y;}
template<typename T>T Max(T x,T y) {return x > y ? x : y;}
template<typename T>void Swap(T &x,T &y) {T z = x;x = y;y = z;}

const int MOD = 1e9 + 7;

long long n,m;
int t,k,tot1,tot2;
int b[65],c[65];
int f[65][2][2][2][2];

int dfs(int len,int up1,int up2,int app,int can) {
	if (!len) return app;
	if (~f[len][up1][up2][app][can]) return f[len][up1][up2][app][can];
	int mdig1 = up1 ? b[len] : k - 1;
	int mdig2 = up2 ? c[len] : k - 1;
	int res = 0;
	for (int i = 0 ; i <= mdig1 ; ++ i) {
		for (int j = 0 ; j <= mdig2 ; ++ j) {
			if (j > i && !can) continue;
			res += dfs(len - 1,up1 && i == mdig1,up2 && j == mdig2,app || (j > i),can || (i > j));
			res = res > MOD ? res - MOD : res;
		}
	}
	return f[len][up1][up2][app][can] = res;
}

int DP(long long x,long long y) {
	memset(f,-1,sizeof f);
	if (y > x) y = x;
	memset(b,0,sizeof b);
	memset(c,0,sizeof c);
	tot1 = tot2 = 0;
	while (x) b[++ tot1] = x % k,x /= k;
	while (y) c[++ tot2] = y % k,y /= k;
	return dfs(tot1,1,1,0,0);
}

int main () {
	read(t);read(k);
	while (t --) {
		read(n);read(m);
		print(DP(n,m)),putchar('\n');
	}
	fwrite(obuf,O - obuf,1,stdout);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78