洛谷P6669 [清华集训2016] 组合数问题题解

题目链接：P6669 [清华集训2016] 组合数问题

题意：

给定 $n,m$ 和 $k$，对于 $0≤i≤n,0≤j≤\min(i,m)$

求有多少对 $(i,j)$ 满足 $\dbinom{i}{j}$ 是 $k$ 的倍数。答案对 $10^9+7$ 取模。

输入格式：

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

接下来 $t$ 行每行两个整数 $n,m$。

输出格式：

共 $t$ 行，每行一个整数代表所有的 $0≤i≤n,0≤j≤\min(i,m)$ 中有多少对 $(i,j)$ 满足 $C^j_i$ 是 $k$ 的倍数。

数据范围：

$1≤n,m≤10^{18}$，$1≤t,k≤100$，且 $k$ 是一个质数。

根据 Lucas 定理

$\binom{n}{m} \equiv\binom{\left\lfloor n/k\right\rfloor}{\left\lfloor m/k\right\rfloor} \times\binom{ n \bmod k}{m \bmod k} \pmod{k}$

这显然是一个与 $k$ 进制有关的拆分。不妨令 $m \gets \min(n,m)$ 。

记 $n$ 在 $k$ 进制下为 $a_la_{l-1}\cdots a_1$ ，并记 $m$ 在 $k$ 进制下为 $b_lb_{l-1}\cdots b_1$ ，那么

$\binom{n}{m} \equiv \prod_{i=1}^l \binom{a_i}{b_i} \pmod{k}$

可以发现，这个式子中只要有一个 $\dbinom{a_i}{b_i}=0$ ， $\dbinom{n}{m}$ 就是 $k$ 的倍数。

由于 $0 \le a_i,b_i < k$ ，所以 $\dbinom{a_i}{b_i}=0$ 当且仅当 $a_i < b_i$ 。

那么问题就转化为，求有多少对 $(i,j)$ 满足 $i$ 在 $k$ 进制下的至少一位比 $j$ 在 $k$ 进制下的那一位小。

这个东西很显然可以容斥，转为求 $i$ 每一位都不小于 $j$ 的方案数，这个可以通过数位dp得到。

即设 $f(i,0/1,0/1)$ 表示考虑到第 $i$ 位，$a_i$ 是否有限制， $b_i$ 是否有限制时的方案数。

转移的话，直接枚举 $a_i,b_i$ ，保证 $a_i \ge b_j$ 即可，这部分是 $\mathcal{O}(k^2)$ 的。那么答案就是

$\frac{(m+1)(m+2)}{2} + (n-m)(m+1) - f(l,1,1) \pmod k$

时间复杂度 $\mathcal{O}(T\cdot 4 k^2\log_k n)$

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
const int mod = 1e9 + 7, inv2 = (mod + 1) / 2;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
template<typename T> void add(T &x, T y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(66))

int k, a[N], b[N]; ll f[N][2][2];
ll dfs(int u, bool ln, bool lm)
{
    if(!u) return 1;
    ll &res = f[u][ln][lm]; if(~res) return res; else res = 0;
    int upn = ln ? a[u] : k - 1, upm = lm ? b[u] : k - 1;
    rep(i, 0, upn) rep(j, 0, min(i, upm))
        add(res, dfs(u - 1, ln && i == upn, lm && j == upm));
    return res;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq >> k;
    while(qwq--)
    {
        ll n, m; cin >> n >> m; down(m, n);
        ll r = (m + 1) % mod * ((m + 2) % mod) % mod * inv2 % mod;
        add(r, (n - m) % mod * ((m + 1) % mod) % mod);
        memset(f, -1, sizeof(f)); int len1 = 0, len2 = 0;
        while(n) { a[++len1] = n % k, n /= k; }
        while(m) { b[++len2] = m % k, m /= k; }
        rep(i, len2 + 1, len1) b[i] = 0;
        cout << (r + mod - dfs(len1, true, true)) % mod << '\n';
    }
    return 0;
}