lightoj1067

maksyuki 发表于 oj 分类，标签: 组合数学-组合数取模(Lucas)

27 8月 2015

1067 - Combinations

For example, say there are 4 items; you want to take 2 of them. So, you can do it 6 ways.Given n different objects, you want to take k of them. How many ways to can do it?

Input

Input starts with an integer T (≤ 2000), denoting the number of test cases.

Each test case contains two integers n (1 ≤ n ≤ 10⁶), k (0 ≤ k ≤ n).

Output

For each case, output the case number and the desired value. Since the result can be very large, you have to print the result modulo 1000003.

Sample Input	Output for Sample Input
34 25 06 4	Case 1: 6Case 2: 1Case 3: 15

题目类型：组合数取模(Lucas)

算法分析：由于模值p不算太大且为质数，则可以使用Lucas定理求解

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 1000000 + 3;

const int maxn = 1000000 + 66;

long long mult_mod (long long a,long long b,long long mod)
{
    a %= mod;
    b %= mod;
    long long ans = 0;
    long long temp = a;

    while (b)
    {
        if (b & 1)
        {
            ans += temp;
            if (ans > mod)
                ans -= mod;
        }

        temp <<= 1;
        if (temp > mod)
            temp -= mod;
        b >>= 1;
    }

return ans;
}

long long pow_mod (long long a,long long n,long long mod)
{
    long long ans = 1;
    long long temp = a % mod;
    while (n)
    {
        if (n & 1)
            ans = mult_mod (ans, temp, mod);

        temp = mult_mod (temp, temp, mod);
        n >>= 1;
    }

return ans;
}

long long fac[maxn];//注意fac数组的大小一定要小于模值p

//在调用Lucas之前一定要先调用GetFactor函数
long long GetFactor (long long p)
{
    fac[0] = 1;
    for (long long i = 1; i <= p; i++)
        fac[i] = (fac[i-1] * i) % p;
}

long long Lucas (long long n, long long m, long long p)
{
    long long ret = 1;
    while (n && m)
    {
        long long a = n % p, b = m % p;
        if (a < b)
            return 0;

        ret = (ret * fac[a] * pow_mod (fac[b] * fac[a-b] % p, p - 2, p)) % p;
        n /= p;
        m /= p;
    }

return ret;
}

int main()
{
//    ifstream cin ("aaa.txt");
//    freopen ("aaa.txt", "r", stdin);

    GetFactor (MOD);

    long long flag = 1, t, n, k;
    scanf ("%lld", &t);

    while (t--)
    {
        scanf ("%lld%lld", &n, &k);
        printf ("Case %lld: %lld\n",  flag++, Lucas (n, k, MOD));
    }

return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 1000000 + 3;

const int maxn = 1000000 + 66;

long long mult_mod (long long a,long long b,long long mod)

{

a %= mod;

b %= mod;

long long ans = 0;

long long temp = a;

while (b)

{

if (b & 1)

{

ans += temp;

if (ans > mod)

ans -= mod;

}

temp <<= 1;

if (temp > mod)

temp -= mod;

b >>= 1;

}

return ans;

}

long long pow_mod (long long a,long long n,long long mod)

{

long long ans = 1;

long long temp = a % mod;

while (n)

{

if (n & 1)

ans = mult_mod (ans, temp, mod);

temp = mult_mod (temp, temp, mod);

n >>= 1;

}

return ans;

}

long long fac[maxn];//注意fac数组的大小一定要小于模值p

//在调用Lucas之前一定要先调用GetFactor函数

long long GetFactor (long long p)

{

fac[0] = 1;

for (long long i = 1; i <= p; i++)

fac[i] = (fac[i-1] * i) % p;

}

long long Lucas (long long n, long long m, long long p)

{

long long ret = 1;

while (n && m)

{

long long a = n % p, b = m % p;

if (a < b)

return 0;

ret = (ret * fac[a] * pow_mod (fac[b] * fac[a-b] % p, p - 2, p)) % p;

n /= p;

m /= p;

}

return ret;

}

int main()

{

// ifstream cin ("aaa.txt");

// freopen ("aaa.txt", "r", stdin);

GetFactor (MOD);

long long flag = 1, t, n, k;

scanf ("%lld", &t);

while (t--)

{

scanf ("%lld%lld", &n, &k);

printf ("Case %lld: %lld\n", flag++, Lucas (n, k, MOD));

}

return 0;

}

lightoj1062

lightoj1070

超客的水墨烟雨

lightoj1067

Input

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论

2024年4月
一	二	三	四	五	六	日
« 6月
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