CF57C Array，排列组合/dp +逆元

思路一：

从1~n中选几个数但这几个数的顺序不变

我们把1和|的序列看作一个组合

如1||11表示一个1，零个2，两个3

共2n-1个位置放n个1，n-1个隔板|

所以就有 $C_{2n-1}^{n}$ 情况，

然后对称性，加上不增序列共 $2C_{2n-1}^{n}$ ，其中有n个同一数序列重复计算，如 1 1 1 1 1 1 1...

所以减掉重复的一共 $2C_{2n-1}^{n}-n=2\frac{A_{2n-1}^{n}}{n!}-n=2\frac{(2n-1)!}{(n-1)!n!}-n=\frac{2n(2n-1)!}{n(n-1)!n!}-n=\frac{2n!}{n!n!}-n=C_{2n}^{n}-n$

思路二：

$f[前i个数][最后是j]$

$f[1][j]=1$

$f[i][j]=\sum_{j}^{k=1}{f[i-1][k]}$

$ans=\sum_{i=1}^{n}{f[n][i]}=f[n+1][n]$

f【1e5】【1e5】是肯定超时的

打表找下规律

杨辉三角

所以f【i】【j】=C（i+j-1，j）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=2e5+10,mod=1e9+7;
ll n;
ll fact[N];

ll qmi(ll a,ll b,ll mod){
	ll ans=1;
	while(b){
		if(b&1){
			ans=(ans*a)%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}

int main(){
	cin>>n;
	fact[0]=1;
	for(int i=1;i<=n<<1;i++) fact[i]=fact[i-1]*i%mod;
	cout<<(fact[n<<1]*qmi(fact[n]*fact[n]%mod,mod-2,mod)-n)%mod;//错误：qmi(fact[n],(mod-2)<<1,mod)
    return 0;
}