我们爱数数

场上部分分状压MLE,难受。

zzs的六维dp无敌虽然这篇题解也是六维dp

$ f[i][j][k1][k2][b][e] $表示当前考虑到第i位,已经至少有j个放置,i + 1位上放置状态为k1,i + 2位上状态为k2,第一位状态b,第二位状态e。

转移到i + 1有四种情况:

不放置。

k1 == 0时在k1放置

i i + 1 i + 2
1 k2 0

k2 == 0时在k2放置

i i + 1 i + 2
k1 1 0

在i + 2放置

i i + 1 i + 2
k1 k2 1

转移后设$ g[i] = \sum f[n][i][k1][k2][b][e]$,表示放置个数>=i的方案。

这时容斥一下,设$ l > i $ ,$ g[l] $对$ g[i] $产生的贡献是$ C_{l}^{i} \times g[l] $。减掉就好了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
typedef long long LL;
#define rep(i,a,b) for(int i = a;i <= b;++i)
#define per(i,a,b) for(int i = a;i >= b;--i)
const int N = 1010,P = 1e9+7;
int n,k,f[N][N][2][2][2][2],g[N],frc[N],inv[N],ans = 0;
inline int gi()
{
int r = 0,s = 1;char c = getchar();for(;!isdigit(c);c = getchar()) if(c == '-') s = 0;
for(;isdigit(c);c = getchar()) r = (((r << 2) + r) << 1) + (c ^ '0');return s ? r : -r;
}
inline void U(int &x,int y){if((x += y) >= P) x -= P;}
inline void D(int &x,int y){if((x -= y) < 0) x += P;}
inline int qpow(int a,int b)
{
int r = 1;for(;b;b >>= 1)
{
if(b & 1) r = 1LL * r * a % P;
a = 1LL * a * a % P;
}
return r;
}
inline void init()
{
frc[0] = 1;rep(i,1,N - 1)frc[i] = 1LL * frc[i - 1] * i % P;
inv[N - 1] = qpow(frc[N - 1],P - 2);per(i,N - 1,1)inv[i - 1] = 1LL * inv[i] * i % P;
}
inline int C(int x,int y){return 1LL * (1LL * frc[y] * inv[x] % P) * inv[y - x] % P;}
int main()
{
init();n = gi();k = gi();
printf("%d\n",inv[1]);
f[1][0][0][0][0][0] = f[1][1][1][0][1][0] = f[1][1][0][1][0][0] = f[1][1][0][0][0][1] = 1;
rep(i,1,n - 1) rep(j,0,n - 1) rep(k1,0,1) rep(k2,0,1) rep(b,0,1) rep(e,0,1)
{
int u = f[i][j][k1][k2][b][e];if(!u) continue;
U(f[i + 1][j][k2][0][b][e],u);
if(!k1)
{
int v = i;
if((v != 1 || !b) && (v != n || !e)) U(f[i + 1][j + 1][k2][0][b || v == 1][e || v == n],u);
}
if(!k2)
{
int v = i % n + 1;
if((v != 1 || !b) && (v != n || !e)) U(f[i + 1][j + 1][1][0][b || v == 1][e || v == n],u);
}
int v = (i + 1) % n + 1;
if((v != 1 || !b) && (v != n || !e)) U(f[i + 1][j + 1][k2][1][b || v == 1][e || v == n],u);
}
rep(j,k,n) rep(k1,0,1) rep(k2,0,1) rep(b,0,1) rep(e,0,1) U(g[j],1LL * frc[n - j] * f[n][j][k1][k2][b][e] % P);
per(i,n,k){rep(j,i + 1,n) D(g[i],1LL * g[j] * C(i,j) % P);U(ans,g[i]);}
printf("%d\n",ans);
return 0;
}