[luogu p2282] combinatorial number problem

Portal

Combinatorial number problem

Title Description

The combination number \ (\ binom {n} {m} \) represents the number of schemes for selecting \ (m \) items from \ (n \) items. For example, selecting two items from three items of \ ((1,2,3) \) can have three selection methods of \ ((1,2), (1,3), (2,3) \). According to the definition of combinatorial number, we can give a general formula for calculating combinatorial number \ (\ binom{n}{m} \):

\[\binom{n}{m}=\frac{n!}{m!(n-m)!} \]

Where \ (n!=1\times2\times\cdots\times n \); In particular, define \ (0! = 1 \).

XiaoCong wants to know how many pairs of \ ((i,j) \) satisfy \ (k|\binom{i}{j} \) for all \ (0 \ Leq I \ Leq n, 0 \ Leq J \ Leq \ min \ left (I, m \ right) \) given \ (n,m \) and \ (K \).

Input / output format

Input format

The first line has two integers \ (t,k \), where \ (t \) represents the total number of groups of test data at the test point. See the problem description for the meaning of \ (k \).

Next, there are two integers \ (n,m \) in each line of \ (t \), where the meaning of \ (n,m \) is shown in the problem description.

Output format

There are \ (t \) lines in total, and an integer in each line represents how many pairs of \ ((i,j) \) in all \ (0 \ Leq, I \ Leq n, 0 \ Leq, J \ Leq \ min \ left (I, m \ right) \) meet \ (k|\binom{i}{j} \).

Sample input and output

Input samples #1

1 2
3 3

Output sample #1

1

Input samples #2

2 5
4 5
6 7

Output samples #2

0
7

explain

[example 1 Description]

Of all possible cases, only \ (\ binom{2}{1} = 2 \) is a multiple of \ (2 \).

[subtask]

  • For all test points, ensure \ (0 \leq n, m \leq 2 \times 10^3 \), \ (1 \leq t \leq 10^4 \).

analysis

This question needs to be answered by \ (\ operatorname{O}(n ^ 2) \) preprocessing \ (\ operatorname{O}(1) \), so how to do it?

Firstly, Yang Hui triangle is used to preprocess the modular results of all combined number pairs \ (k \) in 2000. As follows:

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

Then carefully observe what the topic requires:

For all \ (0 \ Leq I \ Leq n, 0 \ Leq J \ Leq \ min \ left (I, m \ right) \), how many pairs of \ ((i,j) \) satisfy \ (k|\binom{i}{j} \).

For the convenience of discussion, if \ (M > n \), we have a law \ (n \rightarrow m \).

Define \ (ans_{i, j} \) as the answer array, and use the two-dimensional prefix and to get the formula:

\[ans_{i, j} = ans_{i - 1, j} + ans_{i, j - 1} - ans_{i - 1, j - 1} \]

Of course, if we find \ (k|\binom{i}{j} \), then \ (ans_{i, j} \) needs to increase by \ (1 \).

We can write such code:

void init(int k) {
    c[0][0] = c[1][0] = c[1][1] = 1;
    for (int i = 2; i < maxn; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % k;
            ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1];
            if (c[i][j] == 0) ++ans[i][j];
        }
    }
}

But is it over?

If so, submit the program and you will find that your code can get it A good score of 15 points.

Why?

Let's look at the table of ans when \ (k = 5 \). (the first 10 * 10 are listed here)

Obviously, the value of the green square is red + blue purple. But did you find that the location of the Red Square is beyond the preprocessing range of Yang Hui triangle. (the lower left corner of orange is the preprocessing range and the upper right corner is the non preprocessing range), that is, when \ (i = j \), \ (ans_{i - 1, j} \) is not processed.

However, this thing is actually easy to handle because \ (ANS {I + 1, J} = ans {I, J} \). As for why, see its definition:

For all \ (0 \ Leq I \ Leq n, 0 \ Leq J \ Leq \ min \ left (I, m \ right) \), how many pairs of \ ((i,j) \) satisfy \ (k|\binom{i}{j} \).

Have you observed this \ (min(i, m) \)? This means that when \ (M > n \), \ (ANS {m, n} \) and \ (ANS {n, n} \) are actually equivalent.

For the same reason, you can get \ (ANS {I + 1, J} = ans {I, J} \). Therefore, just add an ans[i][i + 1] = ans[i][i] at the end of the I loop; Just. The code is as follows:

void init(int k) {
    c[0][0] = c[1][0] = c[1][1] = 1;
    for (int i = 2; i < maxn; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % k;
            ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1];
            if (c[i][j] == 0) ++ans[i][j];
        }
        ans[i][i + 1] = ans[i][i];
    }
}

In this way, you can AC ~ the last overall code!

code

/*
 * @Author: crab-in-the-northeast 
 * @Date: 2020-10-01 14:01:33 
 * @Last Modified by: crab-in-the-northeast
 * @Last Modified time: 2020-10-01 16:18:48
 */
#include <iostream>
#include <cstdio>

const int maxn = 2005;
const int maxm = 2005;
long long c[maxn][maxm], ans[maxn][maxm];

void init(int k) {
    c[0][0] = c[1][0] = c[1][1] = 1;
    for (int i = 2; i < maxn; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j) {
            c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % k;
            ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1];
            if (c[i][j] == 0) ++ans[i][j];
        }
        ans[i][i + 1] = ans[i][i];
    }
}

int main() {
    int t, k;
    std :: scanf("%d %d", &t, &k);
    init(k);
    while (t--) {
        int n, m;
        std :: scanf("%d %d", &n, &m);
        std :: printf("%lld\n", ans[n][m > n ? n : m]);
    }
    return 0;
}

Evaluation record

Evaluation record

Tags: number theory

Posted by ekosoftco on Sat, 14 May 2022 04:57:33 +0300