题目链接：
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 = ;
typedef long long LL;
int n;
//扩展欧几里得
void gcd(int a, int b, int &d, int &x, int &y) {
if (!b) { d = a; x = ; y = ; }
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 = ;
while (_n--) {
ret *= x;
ret %= mod;
x--;
}
return ret;
} int main() {
while (scanf("%d", &n) == && n) {
int ans = (LL)solve(n, * n - )*inv(solve(n,n))%mod;
ans = ans * - n;
ans = (ans%mod + mod) % mod;
printf("%d\n", ans);
}
return ;
}