にこうけいすう

11050

この係数を求める方法はいくつかありますが、backtrackingで解いて記憶することにしました.

#include <iostream>
#include <vector>
using namespace std;

int n, m, count;
vector<int> vec;

void pick (int curr, int cnt) {
    if (cnt == m) {
        count++;
        return;
    }
    if (curr == n) return;

    vec.push_back(curr);
    pick(curr + 1, cnt + 1);
    vec.pop_back();

    pick(curr + 1, cnt);
}

int main() {
    cin >> n >> m;

    pick(0 ,0);
    cout << count;
}

pick関数は、backtrackingとして5のうち2つを選択するために使用されます.本来ならcount++の位置で、coutであれ何であれ、問題の条件に合えばいいのですが、とにかくこのように解けるのです.

11051

今回の問題は,出力数がより大きく,10007の残りに分かれることである.
単純に既存のプールに%10007を追加すると、タイムアウトになります.
タイムアウトが大嫌いです.
調べてみましたが、これはパスカルの三角形で解けた問題です.とっくに知っていたのにもっと数学の授業に励んだ.

#include <iostream>
#define MAX 1010
using namespace std;

int n, k;
int dp[MAX][MAX];

int main() {
    cin >> n >> k;

    if (n == 0) {
        cout << 0;
        exit(0);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (j == 0) dp[i][j] = 1;
            else if (i == j) dp[i][j] = 1;
            else dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
    }
    cout << dp[n][k] % 10007;
}

問題は、私はこの係数を10007の値で割ることを要求しているのに、この係数だけを要求して10007で割ると間違っていると思っています.
実は.

#include <iostream>
#define MAX 1010
using namespace std;

int n, k;
int dp[MAX][MAX];

int main() {
    cin >> n >> k;

    if (n == 0) {
        cout << 0;
        exit(0);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            if (j == 0) dp[i][j] = 1;
            else if (i == j) dp[i][j] = 1;
            else dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

            dp[i][j] = dp[i][j] % 10007;
        }
    }
    cout << dp[n][k] % 10007;
}

各dpに基づいて、この係数は10007に分けるべきである.
どうしたんですか。