Algoogle

Algorithm for Programming Contest

JOI 春合宿 2011 Keycards

Category: JOI Tag: math

Keycards

問題概要


n箇所のうちいくつかに穴を開けたカードがある.
今そのようなカードをいくつか受け取る.
このときどのカードもちょうどk箇所の同じ場所に穴が空いている.
そのような組合せはいくつあるか.

解法


まずk箇所を固定して考える(最後にその組合せを掛ければよい).
他の残りn-k箇所を考える.

手に入れた全てのカードのn-k箇所のうち左からi箇所に穴が空いているとする.
他のn-k-i箇所が取りうる場合の数(つまりそのようなカードキーの数)は通り.
そこからどれを選ぶかは通り(i+1個以上穴が空く場合も含まれる).
これからi+1箇所穴が空いてるとする場合の選び方を引いてやればi+1個穴が開いてる場合が消せるのでそれをi+1箇所の組合せでやる.
これはi+2箇所やつ以降では余計に引かれている.
さらにそれをi箇所の組合せ全てでやる.
これをi=0から順にやっていけばよい

例えば
n=3, k=1の場合, 1が穴が空いているとすると
i=0で
00
01
10
11
から任意個選んだ場合の数
i=1で
10
11
から任意個選んだ場合の数を引けば1*(*はなんでもよい)となる場合を引ける.
同様に
01
11
の場合も引いてやると*1となる場合を引ける.
i=2で
11
から任意個選んだ場合を足せば前で引きすぎた11となる場合を消せる.

以上を踏まえると以下の式で求めることができる(穴が0個の場合のみになるように足し引きする)

2の冪の冪(2の(2のi乗)乗)は2, 4, 16, 256…となるので前計算しておく

この方法だとn=kの場合は全て穴が空いてない場合を使えてしまうが, どうせ1なのでそのまま返す.
またn=1のときはk=0の場合も使えてしまうがこれもどうせ0なのでそのまま返す.

コード


(keycards.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;
struct mint
{
        int x;
        mint():x(0){}
        mint(int y){ if((x=y%mod+mod) >= mod) x-= mod;}

        mint &operator+=(const mint &m){ if((x += m.x) >= mod) x-=mod; return *this;}
        mint &operator-=(const mint &m){ if((x += mod-m.x) >= mod) x-=mod; return *this;}
        mint &operator*=(const mint &m){ x = 1LL*x*m.x%mod; return *this;}
        mint &operator/=(const mint &m){ x=(1LL*x*ex(m,mod-2).x)%mod; return *this;}
        mint operator+(const mint &m)const{ return mint(*this) += m;}
        mint operator-(const mint &m)const{ return mint(*this) -= m;}
        mint operator*(const mint &m)const{ return mint(*this) *= m;}
        mint operator/(const mint &m)const{ return mint(*this) /= m;}
        bool operator<(const mint &m)const{ return x < m.x;}
        bool operator>(const mint &m)const{ return x > m.x;}
        bool operator==(const mint &m)const{ return x == m.x;}
        bool operator&&(const mint &m)const{ return x && m.x;}
        bool operator||(const mint &m)const{ return x || m.x;}
        mint inv() { return ex(mint(x),mod-2);}
        mint ex(mint a, long long t){
                if(!t) return 1;
                mint res = ex(a,t/2);
                res *= res;
                return (t&1)?res*a:res;
        }
};
ostream &operator<<(ostream& os, const mint &m){ os << m.x; return os;}

int n, k;
mint fact[1000010], p22[1000010]; // p22[i] : 2^(2^i)

void gen()
{
        fact[0] = 1;
        for (int i = 0; i < n; i++) fact[i+1] = fact[i]*(i+1);
        p22[0] = 2;
        for (int i = 0; i < n; i++) p22[i+1] = p22[i]*p22[i];
}

mint comb(int a, int b)
{
        return fact[a]/fact[b]/fact[a-b];
}

mint g(int m, int i)
{
        return comb(m,i)*p22[m-i];
}

mint solve()
{
        if(n == k) return 1;
        if(n == 1) return 0;
        gen();
        mint ans = 0, p = 1, np = mod-1;
        for (int i = 0; i <= n-k; i++) {
                ans += p*g(n-k,i);
                swap(p,np);
        }
        return comb(n,k)*ans;
}

void input()
{
        cin >> n >> k;
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments