[蓝桥杯][2019年第十届真题]组合数问题（数位dp，卢卡斯定理）
个人题解链接，历届试题，正在更新中~
题目描述
给n,m,k，求有多少对
(
i
,
j
)
(i,j)
(i,j)满足
1
≤
i
≤
n
,
0
≤
j
≤
m
i
n
(
i
,
m
)
1 ≤ i ≤ n,0 ≤ j ≤ min(i,m)
1≤i≤n,0≤j≤min(i,m)且
C
(
i
,
j
)
≡
0
(
m
o
d
k
)
C(i,j) ≡ 0(mod k)
C(i,j)≡0(modk)，k 是质数。其中
C
(
i
,
j
)
C(i,j)
C(i,j) 是组合数，表示从 i 个不同的数中选出j个组成 一个集合的方案数。
输入
第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中 相同。
接下来 t 行每行两个整数 n, m，表示一组询问。
输出
输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答 案除以
1
0
9
+
7
10^9 + 7
109+7的余数。
样例输入
1 2
3 3
样例输出
1
数据范围
n
,
m
≤
1
0
18
,
t
≤
1
0
5
n,m ≤ 10^{18}, t ≤ 10^5
n,m≤1018,t≤105
思路
n和m很大，所以我们先想到卢卡斯定理。
化成p进制后，任意一个数都不可能是p的倍数，所以要使其和0同余一定是某一位上n<m的情况，（组合数中规定C(n,m)，若n< m则结果为0）.
所以题目意思转化为小于n和m的p进制数中有多少对数（i，j）i > j 且i中至少一位小于j，然后就可以愉快的数位dp了。在这里我们可以求它的对立，求i>=j,且i每一位都大于j的对数。由于p很大，所以不能使用记忆化搜索。所以只能推一波了。
转移方程：
定义三个函数
- LL calc(LL x, LL y) //x取值[0, x], y取值[0,y] x >=y的数量
- LL calc1(LL x, LL y) // x不变，y取值为[0,y] x >= y的数量
- LL calc2(LL x, LL y) // y不变 x取值为[0,x] x >= y的数量
-
d
p
[
i
]
[
0
]
dp[i][0]
dp[i][0] :第i位无限制。
d
p
[
i
]
[
0
]
=
d
p
[
i
−
1
]
[
0
]
∗
c
a
l
c
(
p
−
1
,
p
−
1
)
+
d
p
[
i
−
1
]
[
1
]
∗
c
a
l
c
(
a
[
i
]
−
1
,
p
−
1
)
+
d
p
[
i
−
1
]
[
2
]
∗
c
a
l
c
(
p
−
1
,
b
[
i
]
−
1
)
+
d
p
[
i
−
1
]
[
3
]
∗
c
a
l
c
(
a
[
i
]
−
1
,
b
[
i
]
−
1
)
，
要
使
第
i
位
无
限
制
，
可
以
从
上
一
位
的
无
限
制
转
移
过
来
，
也
可
以
从
i
到
达
上
界
的
数
组
转
移
过
来
，
但
是
不
能
取
a
[
i
]
，
因
为
取
了
的
话
就
不
能
叫
做
无
限
制
了
,
这
一
位
有
了
一
个
限
制
不
能
超
过
a
[
i
]
，
后
面
两
项
同
理
dp[i][0] = dp[i-1][0]*calc(p-1,p-1)+dp[i-1][1]*calc(a[i]-1,p-1) + dp[i-1][2]*calc(p-1,b[i]-1) + dp[i-1][3]*calc(a[i]-1,b[i]-1)，要使第i位无限制，可以从上一位的无限制转移过来，也可以从i到达上界的数组转移过来，但是不能取a[i]，因为取了的话就不能叫做无限制了,这一位有了一个限制不能超过a[i]，后面两项同理
dp[i][0]=dp[i−1][0]∗calc(p−1,p−1)+dp[i−1][1]∗calc(a[i]−1,p−1)+dp[i−1][2]∗calc(p−1,b[i]−1)+dp[i−1][3]∗calc(a[i]−1,b[i]−1)，要使第i位无限制，可以从上一位的无限制转移过来，也可以从i到达上界的数组转移过来，但是不能取a[i]，因为取了的话就不能叫做无限制了,这一位有了一个限制不能超过a[i]，后面两项同理 -
d
p
[
i
]
[
1
]
dp[i][1]
dp[i][1] :n的前i位为上界，m未达上界 。
d
p
[
i
]
[
1
]
=
d
p
[
i
−
1
]
[
1
]
∗
c
l
a
c
1
(
a
[
i
]
,
p
−
1
)
+
d
p
[
i
−
1
]
[
3
]
∗
c
a
l
c
1
(
a
[
i
]
,
b
[
i
]
−
1
)
dp[i][1] = dp[i-1][1]*clac1(a[i], p-1) + dp[i-1][3]*calc1(a[i], b[i]-1)
dp[i][1]=dp[i−1][1]∗clac1(a[i],p−1)+dp[i−1][3]∗calc1(a[i],b[i]−1)要
使
n
始
终
为
上
界
，
那
么
可
以
从
两
个
地
方
转
移
过
来
，
前
一
个
有
限
制
的
在
这
里
还
是
取
了
a
[
i
]
,
所
以
还
是
有
限
制
。
都
有
限
制
的
，
使
得
a
[
i
]
到
达
限
制
b
[
i
]
不
到
达
限
制
就
可
以
转
到
这
个
状
态
。
要使n始终为上界，那么可以从两个地方转移过来，前一个有限制的在这里还是取了a[i],所以还是有限制。都有限制的，使得a[i]到达限制b[i]不到达限制就可以转到这个状态。
要使n始终为上界，那么可以从两个地方转移过来，前一个有限制的在这里还是取了a[i],所以还是有限制。都有限制的，使得a[i]到达限制b[i]不到达限制就可以转到这个状态。 -
d
p
[
i
]
[
2
]
dp[i][2]
dp[i][2]:m的前i位都为上界，n未达上界。
d
p
[
i
]
[
2
]
=
d
p
[
i
−
1
]
[
2
]
∗
c
l
a
c
2
(
p
−
1
,
b
[
i
]
)
+
d
p
[
i
−
1
]
[
3
]
∗
c
l
a
c
2
(
a
[
i
]
−
1
,
b
[
i
]
)
dp[i][2] = dp[i-1][2]*clac2(p-1, b[i]) + dp[i-1][3]*clac2(a[i]-1, b[i])
dp[i][2]=dp[i−1][2]∗clac2(p−1,b[i])+dp[i−1][3]∗clac2(a[i]−1,b[i]) -
d
p
[
i
]
[
3
]
dp[i][3]
dp[i][3]:n，m都到达了上界。
d
p
[
i
]
[
3
]
&
=
a
[
i
]
>
b
[
i
]
dp[i][3] \&= a[i] > b[i]
dp[i][3]&=a[i]>b[i] 因为要使的n的每一位都大于m。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double Pi = acos(-1);
namespace {
template <typename T> inline void read(T &x) {
x = 0; T f = 1;char s = getchar();
for(; !isdigit(s); s = getchar()) if(s == '-') f = -1;
for(; isdigit(s); s = getchar()) x = (x << 3) + (x << 1) + (s ^ 48);
x *= f;
}
}
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define _for(n,m,i) for (register int i = (n); i < (m); ++i)
#define _rep(n,m,i) for (register int i = (n); i <= (m); ++i)
#define _srep(n,m,i)for (register int i = (n); i >= (m); i--)
#define _sfor(n,m,i)for (register int i = (n); i > (m); i--)
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
#define lowbit(x) x & (-x)
#define pii pair<int,int>
#define fi first
#define se second
const LL Mod = 1e9+7;
const LL inv_2 = 5e8+4;
LL dp[65][4];
/*
用卢卡斯定理后转化为n，m的k进制数中，n中至少有一位大于m则模k为0.
考虑对立事件，求出n中所有位都大于m的对数，在用总方案减去它
dp[i][0] :第i位无限制
dp[i][1] :n的前i位为上界，m未达上界
dp[i][2] :m的前i位位上界，n未达上界
dp[i][3] :n，m都到达了上界
*/
LL calc(LL x, LL y) {//x取值[0, x], y取值[0,y] x >=y的数量
if(x < 0|| y < 0) return 0;
if(x < y) {
x %= Mod; y %= Mod;
return (x+2) * (x + 1) % Mod * inv_2 % Mod;
}
x %= Mod; y %= Mod;
return ((y + 2) * (y + 1) % Mod * inv_2 % Mod + (x-y) * (y+1) % Mod) % Mod;
}
LL calc1(LL x, LL y) { // x不变，y取值为[0,y] x >= y的数量
return min(x, y) + 1;
}
LL calc2(LL x, LL y) { // y不变 x取值为[0,x] x >= y的数量
if(x < y) return 0;
return x - y + 1;
}
LL a[100], b[100], P;
int main() {
int t; read(t); read(P);
while(t--) {
LL n, m, ans;
read(n); read(m);
if(m > n) m = n;
ans = calc(n, m);
int lenn = 0, lenm = 0;
while(n) a[lenn++] = n % P, n /= P;
while(m) b[lenm++] = m % P, m /= P;
n = max(lenn, lenm);
memset(dp, 0, sizeof dp);
dp[n][3] = 1;
for(int i = n-1; ~i; i--) {
dp[i][0] = dp[i+1][0] * calc(P-1, P-1) + dp[i+1][1] * calc(a[i]-1, P-1)
+ dp[i+1][2] * calc(P-1, b[i]-1) + dp[i+1][3] * calc(a[i]-1, b[i]-1);
dp[i][1] = dp[i+1][1] * calc1(a[i], P-1) + dp[i+1][3] * calc1(a[i], b[i]-1);
dp[i][2] = dp[i+1][2] * calc2(P-1, b[i]) + dp[i+1][3] * calc2(a[i]-1, b[i]);
dp[i][3] = dp[i+1][3] & (a[i] >= b[i]);
dp[i][0] %= Mod; dp[i][1] %= Mod; dp[i][2] %= Mod;
a[i] = b[i] = 0;
}
ans -= dp[0][0] + dp[0][1] + dp[0][2] + dp[0][3];
ans %= Mod;
if(ans < 0) ans += Mod;
printf("%lld\n", ans);
}
}
/*
1 2
509295295705797874 372612087921270267
265498746
*/
