CodeForces 57C Array 组合计数+逆元

题目链接：

http://codeforces.com/problemset/problem/57/C

题意：

给你一个数n，表示有n个数的序列，每个数范围为[1,n]，叫你求所有非降和非升序列的个数。

题解：

由于对称性，我们只要求非降序的个数就可以了（n个数全部相等的情况既属于非升也属于非降）

我们在满足条件的n个数之前加一个虚节点1，在第n个数之后加一个虚节点n，那么考虑这n+2个数组成的非降序列：

假设序列里的第i个数为a[i]，我们设xi=a[i+1]-a[i]+1，1<=i<=n+1，则满足每个数>=1,且sum(x[1],x[2]...x[n+1])=2*n；

那么相当于求将2*n分成n个部分，且每个部分的值大于等于1，则易得非降序列总数为：C(n,2*n-1)（2*n-1 选 n）

所以最后的答案是2*C(n,2*n-1)-n；

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int mod = 1000000007;
typedef long long LL;
int n;
//扩展欧几里得
void gcd(int a, int b, int &d, int &x, int &y) {
    if (!b) { d = a; x = 1; y = 0; }
    else { gcd(b, a%b, d, y, x); y -= x*(a / b); }
}
//求逆元
int inv(int a) {
    int d, x, y;
    gcd(a, mod, d, x, y);
    return x;
}
//求阶乘
int solve(int _n,int x) {
    LL ret = 1;
    while (_n--) {
        ret *= x;
        ret %= mod;
        x--;
    }
    return ret;
}

int main() {
    while (scanf("%d", &n) == 1 && n) {
        int ans = (LL)solve(n, 2 * n - 1)*inv(solve(n,n))%mod;
        ans = ans * 2 - n;
        ans = (ans%mod + mod) % mod;
        printf("%d
", ans);
    }
    return 0;
}