【问题描述】
小美今天对于数列很有兴趣。小美打算找出一些漂亮的序列。一个漂亮的序列的限制如下：
- 长度为 n ，而且数列里只包含 [1,n] 的整数。
- 要不是不降的序列就是不升的序列。
小美想知道有多少个合法的序列满足要求。
【输入格式】
从文件 pretty.in 中读入数据。
第一行一个正整数 n 表示数列的大小。
【输出格式】
输出到文件 pretty.out 中。
第一行输出一个数字表示答案。由于这个数字会很大，你需要输出他
模 1000000007 。
【样例】
【样例输入】
【样例输出】
【样例输入】
【样例输出】
【题目来源】
题解
首先，看到这样的问题，我们想到这应该是道dp。
我们设\(f[i][j]\)表示前\(i\)个数到达最后一位是\(j\)的递增序列的方案数，则不难根据对称性得出答案为\(2\sum_{i=1}^{n}f[n][i]-n\)，减\(i\)是为了减去递增和递减都包含的情况（即全部相同的请况，那显然是\(i\)）。
我们发现\(f[i][j]\)的状态由所有\(f[i-1][k](k\le j)\)的状态在结尾加上\(k\)转移过来。故转移方程为：\(f[i][j] = \sum_{k=1}^{j}f[i-1][k]\)。
于是暴力程序就打出来了，那么让我们打张表：
#include <cstdio>
const int n = 10;
int f[n+1][n+1];
int main()
{
freopen("biao.out", "w", stdout);
int ans;
for(int i = 1; i <= n; ++i)
f[1][i] = 1;
for(int i = 2; i <= n; ++i)
{
ans = 0;
for(int j = 1; j <= n; ++j)
for(int k = 1; k <= j; ++k)
f[i][j] = f[i][j] + f[i-1][k];
for(int j = 1; j <= i; ++j)
ans = ans+f[i][j];
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
printf("%5d ", f[i][j]);
puts("");
}
}
biao.out
1 1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9 10
1 3 6 10 15 21 28 36 45 55
1 4 10 20 35 56 84 120 165 220
1 5 15 35 70 126 210 330 495 715
1 6 21 56 126 252 462 792 1287 2002
1 7 28 84 210 462 924 1716 3003 5005
1 8 36 120 330 792 1716 3432 6435 11440
1 9 45 165 495 1287 3003 6435 12870 24310
1 10 55 220 715 2002 5005 11440 24310 48620
一看发现：这不是杨辉三角吗？
于是毫不犹豫地打了个\(n^2\)，然后就T飞了。
竟然没想到\(\sum_{i=1}^{n}f[n][i] = f[n+1][n] = C^{n}_{2n}\)（可以直接推，也可以看作是在序列结尾加一个\(n\)进行限制）。
于是答案就变成了\(2C^n_{2n}-n\)。取模要求逆元，用费马小定理做一下，总时间复杂度为\(O(n)\)。
当然，杨辉三角也是可以直接推出来的：
\[f[i][j] = \sum_{k=1}^{j}f[i-1][k] = f[i-1][j] + \sum_{k=1}^{j-1}f[i-1][k] = f[i-1][j] + f[i-1][j-1].
\]
\]
以下是我的代码（由于模拟赛加了文件读入输出）：
#include <fstream>
using namespace std;
typedef long long LL;
ifstream fin("pretty.in");
ofstream fout("pretty.out");
inline LL pow(LL x, LL y, LL mod)
{
LL ans = 1;
for(; y; y >>= 1, x = (x*x)%mod)
if(y & 1)
ans = (ans*x) % mod;
return ans % mod;
}
const LL mod = 1000000007;
const int maxn = 100005;
LL fac[maxn<<1];
int main()
{
LL n;
fin >> n;
fac[0] = 1;
for(int i = 1; i <= (n<<1); ++i)
fac[i] = fac[i-1] * i % mod;
fout << (fac[n<<1]* pow(fac[n]*fac[n]%mod, mod-2, mod)) % mod - n << endl;
return 0;
}