[题解] Permutation
解析
一眼 DP 或者 组合。
70pts
场上推的DP
对于 \((4,2,2)\)，先把所有序列枚举出来：
\[\begin{split} 1\ \ \ 2\\ 1\ \ \ 3\\ 1\ \ \ 4\\ --\\ 2\ \ \ 3\\ 2\ \ \ 4\\ 3\ \ \ 4 \end{split} \]可以发现，对于分割线上的部分，可以看作 \((3,1,1)\) 的所有序列每个数 \(+1\)，然后前导一个 \(1\)。因为答案计算的是绝对值，所以每个数加一相当于整体抬高，不影响答案。而对于分割线下的部分，可以看作 \((3,2,2)\) 的所有序列每个数 \(+1\)，同样不影响答案。令 \(f(i,j,z)\) 表示对应 \((n,k,m)\) 的答案。那么有：
\[f(i,j,z)=f(i-1,j-1,z-1)+f(i-1,j,z)+? \]留个问号是因为，这两部分合并还可以产生贡献，为上面部分最后一个数与下面部分第一个数的差的绝对值。上面部分最后一个数为 \(i\)，下面部分第一个数为 \(j+1\)。所以有：
\[\begin{split} f(i,j,z)&=f(i-1,j-1,z-1)+f(i-1,j,z)+|i-j-1|\\ \end{split} \]\[\begin{split} f(i,i,z)&=0\\ f(i,j,1)&=i-j \end{split} \]但 \(i,j,z\) 都是 \(10^6\) 级别的，空间会炸。可以发现 \(i\) 只和 \(i-1\) 有关，可以滚掉。\(j\) 和 \(z\) 同减，并且 \(z\le j\)，那么只维护最小的 \(z\) 即可。
场码
#include<bits/stdc++.h>
using namespace std;
constexpr int B = 1 << 23;
char buf[B], *p1 = buf, *p2 = buf;
#define gt() (p1==p2 && (p2=(p1=buf)+fread(buf, 1, B, stdin), p1==p2) ? EOF : *p1++)
template <typename T> inline void rd(T &x){
x = 0; int f = 0; char ch = gt();
for(; !isdigit(ch); ch = gt()) f ^= ch == '-';
for(; isdigit(ch); ch = gt()) x = (x<<1) + (x<<3) + (ch^48);
x = f ? -x : x;
}
char obuf[B], *O = obuf;
#define pt(ch) (O-obuf==B && (fwrite(obuf, 1, B, stdout), O=obuf), *O++=(ch))
template <typename T> inline void wt(T x){
if(x < 0) pt('-'), x = -x;
if(x >= 10) wt(x / 10); pt(x % 10 ^ 48);
}
#define fw fwrite(obuf, 1, O - obuf, stdout)
#define ll long long
#define ull unsigned long long
constexpr int N = 1e6 + 5, M = 1e9 + 7;
int n, k, m, f[2][N], lst, now = 1;
int main(){
// freopen("perm.in", "r", stdin);
// freopen("perm.out", "w", stdout);
rd(n), rd(k), rd(m);
if(n == k) wt(m);
else {
int tmp = k - m;
for(int i=tmp; i<=n; ++i){
for(int j=max(1, m+i-n); j+tmp<=i; ++j){
if(j == 1) f[now][j] = i - (j + tmp);
else if(i == j + tmp) f[now][j] = 0;
else f[now][j] = ((ll)f[lst][j] + (ll)f[lst][j-1] + abs(i - j - tmp - 1)) % M;
}
for(int j=max(i, m+i-1-n); j+tmp<=i-1; ++j) f[lst][j] = 0;
now ^= 1, lst ^= 1;
} wt(f[lst][m]);
} return fw, 0;
}
另一种 DP 思路
先打表找规律。打出 \(8\) 以内的表可以发现，答案只和 \(n-m\) 和 \(k\) 相关，那么把 \(k\) 设为横坐标，\(n-m\) 设为纵坐标，于是有：
\[\begin{matrix} 1&2&3&4&5&\cdots\\ 1&4&9&16&25&\cdots\\ 1&6&17&36&65&\cdots\\ 1&8&27&66&135&\cdots\\ 1&10&39&108&247&\cdots\\ 1&12&53&164&415&\cdots\\ \vdots&\vdots&\vdots&\vdots&\vdots&\ddots \end{matrix} \]令 \(f(i,j)\) 表示图上对应横坐标与纵坐标的值。于是有：
\[f(i,j)=f(i-1,j)+f(i,j-1)+j \]注意边界判断：
\[\begin{split} f(1,i)=i+1\\ f(i,0)=0 \end{split} \]答案即为：
\[f(k,n-m-1) \]于是 \(\mathcal{O}(n^2)\) 递推即可。
100pts
考虑优化刚才的那个 DP，可以发现，对于点 \((i,j)\) 的答案可以看作是从这个点一直走到到点 \((0,0)\) 的所有路径的权值总和。这个东西可以用组合求解。可以枚举每一个点 \((i,j)\)，一共有 \(\binom{i+j}{i}\) 条路径经过这一点。对于边界 \(i=1\) 需要特判一下，看作权值为 \(1\)。于是可以列出式子：
\[\sum_{i=0}^{m-2}\sum_{j=0}^{n}(n-j)\binom{i+j}{j}+\sum_{j=0}^{n}\binom{m-1+j}{j} \]但是这个式子是 \(\mathcal{O}(n^2)\) 的。所以考虑优化。有一个公式：
\[\sum_{i=m}^{n}\binom{a+i}{i}=\binom{a+n+1}{n}-\binom{a+m}{m-1} \]用上面的式子套公式即可优化到一维：
\[\sum_{j=0}^{n}\binom{j+m-2}{j+1}+\sum_{j=0}^{n}\binom{m-1+j}{j} \]复杂度 \(\mathcal{O}(n)\)。
code
#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 5, M = 1e9 + 7;
int n, m, k, ans, p[N<<1], inv[N<<1];
#define ll long long
inline int qpow(int a, int k){
int as = 1;
while(k){
if(k & 1) as = (ll)as * a % M;
a = (ll)a * a % M; k >>= 1;
} return as;
}
inline int C(int a, int b){
return (ll)p[a] * inv[b] % M * inv[a-b] % M;
}
int main(){
freopen("perm.in", "r", stdin);
freopen("perm.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m>>k;
if(n == m) return cout<<m, 0;
n -= m + 1;
p[0] = 1; for(int i=1; i<=n+m; ++i) p[i] = (ll)p[i-1] * i % M;
inv[n+m] = qpow(p[n+m], M-2); for(int i=n+m-1; i>=0; --i) inv[i] = (ll)inv[i+1] * (i+1) % M;
if(k >= 2) for(int j=0; j<=n; ++j) ans = ((ll)ans + (ll)(n-j) * C(j+k-1, j+1) % M) % M;
for(int j=0; j<=n; ++j) ans = ((ll)ans + (ll)C(k+j-1, j)) % M;
return cout<<ans, 0;
}