はまやんはまやんはまやん

hamayanhamayan's blog

CODING WAR [yukicoder 391]

競技プログラミング

問題

http://yukicoder.me/problems/no/391

N人のプログラマとM個の問題がある。
問題の担当者を以下のルールのもと決めるとき、担当の決め方は全部で何通りか、10^9+7を法として答えよ。

もし、問題数がプログラマを超えたら反則で0通りとする。

1 <= N <= 10^12
1 <= M <= 10^5

考察

1. 組合せなので、まず、数学的に解けるか考える
2. 解けそうな解けそうにないような…
3. 無理っぽい。DPかな…
4. 無理っぽい。ヤバイぞ…

5. どういう問題に帰着できるかを考える
6. 「N人がM個のうち1つの問題を選択し、かつ、各問題が必ず1人に選ばれる、ときの組合せは？」
7. うーん。式にできないぞ…

ここで発想

8. 組合せ問題で良く出てくるキーワード「包除原理」を元に考えてみる
9. お？これは行けそうだぞ？

(N人がM個から問題を選び、かつ、各問題が必ず1人に選ばれる組合せ)
= (N人がM個から問題を選ぶ組合せ)
+ -(N人がM-1個から問題を選ぶ組合せ)
+ (N人がM-2個から問題を選ぶ組合せ)
...
+ (-1)^i(N人がM-i個から問題を選ぶ組合せ)
...
+ (-1)^(M-1)(N人が1個から問題を選ぶ組合せ)

10. 包除原理を知ってないと厳しい問題かも

実装

http://yukicoder.me/submissions/102382

typedef long long ll;
ll MOD = 1000000007;
const int NUM_FAC = 2000001;
ll modfact(ll x) {
    static ll _fact[NUM_FAC + 1];
    if (_fact[0] == 0) {
        _fact[0] = 1;
        for (int i = 1; i <= NUM_FAC; ++i) _fact[i] = _fact[i - 1] * i%MOD;
    }
    return _fact[x];
}
ll modpow(ll a, ll n) {
    ll r = 1;
    while (n) r = r*((n % 2) ? a : 1) % MOD, a = a*a%MOD, n >>= 1;
    return r;
}
ll moddiv(ll a, ll b)
{
    ll ap_2 = modpow(b, MOD - 2);
    return (a * ap_2) % MOD;
}
ll aCb(ll a, ll b) {
    return moddiv(modfact(a), (modfact(a - b) * modfact(b)) % MOD);
}
//-----------------------------------------------------------------
#define rrep(i,a,b) for(int i=a;i>=b;i--)
ll N, M;
//-----------------------------------------------------------------
int main() {
    cin >> N >> M;

    if (N < M) {
        printf("0\n");
        return 0;
    }

    ll ans = 0;
    int m = 1;
    rrep(i, M, 1) {
        ll t = (aCb(M, i) * modpow(i, N)) % MOD;
        ans += m * t;
        ans = (ans + MOD) % MOD;
        m *= -1;
    }
    cout << ans << endl;
}