挺有收获的一道题ヾ(◍°∇°◍)ﾉﾞ
恰好为 m ，这个限制仿佛不是很好处理。一般而言，我所了解的恰好为 k 的条件，不是用组合数 / dp状态转移 / 斜率二分就只剩下容斥了。我们可以先处理出 num[i] 表示至少有 i 个完美位置的方案数，之后再容斥得到 ans[m] （恰好为 m 个）。如何获得 num 数组？建立dp状态为 f[i][j][p][q], （其中p, q为01状态）表示dp到第 i 个位置，已经出现了 j 个完美的位置，且 i 和 i + 1 是否被用过。转移的时候分情况讨论：1.当前位置不成为完美的位置，直接忽略；2.当前位置填 i - 1 成为一个完美的位置；3.当前位置填 i + 1 成为一个完美的位置。之后把忽略掉的数乘上排列数即可。
这个状态并不是很好想到，但我们主要要明确：第 i 个位置是否成为完美的位置，仅仅与 i - 1 和 i + 1 有关，而也仅有 i + 1 对于后一个位置存在影响。忽略的数字我们可以直接跳过不算，因为当前不用这个数字 i , i 在之后也无法再影响到完美数的形成。至于容斥，我还是只会 \(n^{2}\) 的由至少到恰好的递推……这个 O(n) 的全背背式子吧 :(
\(ans[m] = num[m] - C(m + 1, m) * num[m + 1] ... * (-1)^{n - m} * C(n, m) * num[n]\)
#include <bits/stdc++.h>
using namespace std;
#define maxn 1500
#define int long long
#define mod 1000000007
int n, K, f[maxn][maxn][][], num[maxn];
int ans[maxn], fac[maxn], C[maxn][maxn]; int read()
{
int x = , k = ;
char c; c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
} void Up(int &x, int y) { x = (x + y) % mod; }
void pre()
{
fac[] = ; for(int i = ; i < maxn; i ++) fac[i] = fac[i - ] * i % mod;
for(int i = ; i < maxn; i ++) C[i][] = ;
for(int i = ; i < maxn; i ++)
for(int j = ; j < maxn; j ++)
C[i][j] = (C[i - ][j - ] + C[i - ][j]) % mod;
} signed main()
{
pre(); n = read(), K = read();
f[][][][] = ;
for(int i = ; i < n; i ++)
{
for(int j = ; j <= i; j ++)
for(int p = ; p <= ; p ++)
for(int q = ; q <= ; q ++)
{
Up(f[i + ][j][q][], f[i][j][p][q]);
if(!p) Up(f[i + ][j + ][q][], f[i][j][p][q]);
if(i < n - ) Up(f[i + ][j + ][q][], f[i][j][p][q]);
}
}
for(int i = ; i <= n; i ++)
{
for(int p = ; p <= ; p ++)
for(int q = ; q <= ; q ++)
Up(num[i], f[n][i][p][q]);
num[i] = num[i] * fac[n - i] % mod;
}
ans[K] = num[K];
for(int i = K + , t = -; i <= n; i ++, t *= -)
Up(ans[K], (t * C[i][K] * num[i] % mod) + mod);
/*for(int i = n; i >= K; i --)
{
int t = num[i];
for(int j = n; j > i; j --)
t = (t - (ans[j] * C[j][i]) % mod + mod) % mod;
ans[i] = t;
}*/
printf("%lld\n", ans[K]);
return ;
}