洛谷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;
}