2015年9月9日 星期三

2015/09/09 Codeforces 575H. Bots

/*
    列式之後
    發現是簡單的排列組合
    只是要用上模逆元
*/
// http://codeforces.com/problemset/problem/575/H
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
#define MOD (int)(1e9+7)

int fac[3000000];
int rev[3000000];
int rfac[3000000];

int C(int m, int n)
{
    if( n > m ) return 0;
    return (ll)fac[m]*rfac[n]%MOD*rfac[m-n]%MOD;
}

int main()
{
    fac[0] = 1;
    for(int i = 1; i < 3000000; i++)
        fac[i] = (ll)fac[i-1]*i%MOD;

    rev[1] = 1;
    for(int i = 2; i < 3000000; i++)
        rev[i] = (ll)rev[MOD%i]*(MOD-MOD/i)%MOD;

    rfac[0] = 1;
    for(int i = 1; i < 3000000; i++)
        rfac[i] = (ll)rfac[i-1]*rev[i]%MOD;

    int N;
    scanf("%d", &N);

    int ans = 0;

    for(int Ni = 0; Ni <= N; Ni++)
    {
        ans += C(Ni+N+1, Ni+1);
        ans %= MOD;
    }

    printf("%d\n", ans);
}

沒有留言:

張貼留言