# 组合数问题


**问题描述**

给 n, m, k， 求有多少对(i, j)满足 1 ≤ i ≤ n, 0 ≤ j ≤ min(i, m) 且$C_i^j$≡0(mod k)，k 是质数。其中$C_i^j$是组合数，表示从 i 个不同的数中选出 j 个组成一个集合的方案数。

**输入格式**

第一行两个数 t, k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中相同。

接下来 t 行每行两个整数 n, m，表示一组询问。

**输出格式**

输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答案除以 109 + 7 的余数。

**样例输入**

```
1 2
3 3
```

**样例输出**

```
1
```

**样例说明**

在所有可能的情况中，只有 $C_2^1$ 是 2 的倍数。

**样例输入**

```
2 5
4 5
6 7
```

**样例输出**

```
0
7
```

**样例输入**

```
3 23
23333333 23333333
233333333 233333333
2333333333 2333333333
```

**样例输出**

```
851883128
959557926
680723120
```

**数据规模和约定**

```
对于所有评测用例，1 ≤ k ≤ 108, 1 ≤ t ≤ 105, 1 ≤ n, m ≤ 1018，且 k 是质数。评测时将使用 10 个评测用例测试你的程序
```

以下选项<span style="color:red">错误</span>的是？


## 答案

```c
其他三项都是错的
```

## 选项

### A

```c
const int Mod = 1e9 + 7;
int c[2010][2010];
int main()
{
    int n, m, t, k;
    cin >> t >> k;
    int nn = 2000, mm = 2000;
    for (int i = 0; i <= nn; i++)
    {
        c[i][0] = 1;
        c[i][i] = 1;
    }
    for (int i = 1; i <= nn; i++)
        for (int j = 1; j <= mm; j++)
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % k;
    while (t--)
    {
        cin >> n >> m;
        int ans = 0;
        for (int j = 0; j <= m; j++)
            for (int i = j; i <= n; i++)
                if (c[i][j] == 0)
                    ans++;
        cout << ans % Mod;
    }
    return 0;
}
```

### B

```c
#define modk(x) (((x) >= k) ? ((x)-k) : (x))
const int maxn = 2005;
int c[maxn][maxn], n, m, k, T;
void init()
{

    c[0][0] = 1;
    for (int i = 1; i < maxn; i++)
    {
        c[i][0] = 1 % k;
        for (int j = 1; j <= i; j++)
        {
            c[i][j] = modk(c[i - 1][j] + c[i - 1][j - 1]);
        }
    }

    for (int i = 0; i < maxn; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (c[i][j] == 0)
                c[i][j] = 1;
            else
                c[i][j] = 0;
        }
    }

    for (int i = 1; i < maxn; i++)
    {
        int s = 0;
        for (int j = 0; j < maxn; j++)
        {
            s += c[i][j];
            c[i][j] = c[i - 1][j] + s;
        }
    }
}
int main()
{
    scanf("%d%d", &T, &k);
    init();
    while (T--)
    {
        scanf("%d%d", &n, &m);
        printf("%d\n", c[n][m]);
    }
    return 0;
}
```

### C

```c
const int Mod = 1e9 + 7;
const int inv_2 = 5e8 + 4;

long long cal(long long x, long long y)
{
    if (x < y)
    {
        x %= 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;
}
long long cal_1(long long x, long long y)
{
    return min(x, y) + 1;
}
long long cal_2(long long x, long long y)
{
    if (x < y)
    {
        return 0;
    }
    return x - y + 1;
}

int main()
{
    int t, k;
    cin >> t >> k;
    long long n, m;
    int a[100], b[100];
    for (int turn = 0; turn < t; ++turn)
    {
        cin >> n >> m;
        if (m > n)
            m = n;
        long long ans = cal(n, m);
        int len_a = 0, len_b = 0;
        while (n)
        {
            a[len_a++] = n % k;
            n /= k;
        }
        while (m)
        {
            b[len_b++] = m % k;
            m /= k;
        }
        int len = max(len_a, len_b);
        vector<vector<long long>> dp(len + 1, vector<long long>(4));
        dp[len][3] = 1;
        for (int i = len - 1; i >= 0; --i)
        {
            dp[i][0] = dp[i + 1][0] * cal(k - 1, k - 1) + dp[i + 1][1] * cal(a[i] - 1, k - 1) + dp[i + 1][2] * cal(k - 1, b[i] - 1) + dp[i + 1][3] * cal(a[i] - 1, b[i] - 1);
            dp[i][1] = dp[i + 1][1] * cal_1(a[i], k - 1) + dp[i + 1][3] * cal_1(a[i], b[i] - 1);
            dp[i][2] = dp[i + 1][2] * cal_2(k - 1, b[i]) + dp[i + 1][3] * cal_2(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, dp[i][3] %= Mod;
        }
        ans -= dp[0][0] + dp[0][1] + dp[0][2] + dp[0][3];
        ans %= Mod;
        if (ans < 0)
            ans += Mod;
        cout << ans << endl;
    }
    return 0;
}
```