Codeforces 57C Array dp暴力找到规律

的非增量程序首先，计算，

如果不增加的节目数量x，非减少一些方案是x

答案就是 2*x - n

仅仅需求得x就可以。

能够先写个n3的dp，然后发现规律是 C(n-1, 2*n-1)

然后套个逆元就可以。

#include<iostream>

#include<cstdio>

#include<vector>

#include<string.h>

using namespace std;

#define ll long long

#define mod 1000000007

ll n;

ll Pow(ll x, ll y)

{

    ll ans = 1;

    while(y)

    {

        if(y&1) ans = (ans * x) % mod;

        y >>= 1;

        x = (x*x)%mod;

    }

    return ans;

}

ll chu(ll x, ll y)

{

    return (x * Pow(y, mod-2))%mod;

}

int main(){

	ll i, j;

	while(cin>>n){

        if(n==1){puts("1");continue;}

        n -- ;

        ll ans = n+2;

        ll zi = 2, mu = n+3;

        for(i = n+3; i <= 2*n+1; i++)

        {

            ans *= mu;

            ans = chu(ans % mod, zi);

            mu++; zi++;

        }

        ans *= 2; ans -= (n+1);

        ans += mod;

        cout<<ans%mod<<endl;

	}

	return 0;

}