感觉还是对容斥不够熟悉啊。。
先用轮廓线dp求出f[ i ][ j ]表示 i 行 j 列 没有限制的方案数。
然后2^m枚举列的划分情况进行容斥。
对于每一种情况
t[ i ] 表示这种情况下， i 行没有限制的方案数。
g[ i ]表示这种情况下， i 行并且没有可以划分的行的方案数。
g[ i ] 可以从 t[ i ] 推过来。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include<bits/stdc++.h> #define LL long long #define LD long double #define ull unsigned long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ALL(x) (x).begin(), (x).end() #define fio ios::sync_with_stdio(false); cin.tie(0); using namespace std; const int N = 2e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = (int)1e9 + 7; const double eps = 1e-8; const double PI = acos(-1); template<class T, class S> inline void add(T& a, S b) {a += b; if(a >= mod) a -= mod;} template<class T, class S> inline void sub(T& a, S b) {a -= b; if(a < 0) a += mod;} template<class T, class S> inline bool chkmax(T& a, S b) {return a < b ? a = b, true : false;} template<class T, class S> inline bool chkmin(T& a, S b) {return a > b ? a = b, true : false;} //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int f[17][17] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1}, {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597}, {0, 0, 3, 0, 11, 0, 41, 0, 153, 0, 571, 0, 2131, 0, 7953, 0, 29681}, {0, 1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, 51205, 145601, 413351, 1174500, 3335651, 9475901}, {0, 0, 8, 0, 95, 0, 1183, 0, 14824, 0, 185921, 0, 2332097, 0, 29253160, 0, 366944287}, {0, 1, 13, 41, 281, 1183, 6728, 31529, 167089, 817991, 4213133, 21001799, 106912793, 536948224, 720246619, 704300462, 289288426}, {0, 0, 21, 0, 781, 0, 31529, 0, 1292697, 0, 53175517, 0, 188978103, 0, 124166811, 0, 708175999}, {0, 1, 34, 153, 2245, 14824, 167089, 1292697, 12988816, 108435745, 31151234, 940739768, 741005255, 164248716, 498190405, 200052235, 282756494}, {0, 0, 55, 0, 6336, 0, 817991, 0, 108435745, 0, 479521663, 0, 528655152, 0, 764896039, 0, 416579196}, {0, 1, 89, 571, 18061, 185921, 4213133, 53175517, 31151234, 479521663, 584044562, 472546535, 732130620, 186229290, 274787842, 732073997, 320338127}, {0, 0, 144, 0, 51205, 0, 21001799, 0, 940739768, 0, 472546535, 0, 177126748, 0, 513673802, 0, 881924366}, {0, 1, 233, 2131, 145601, 2332097, 106912793, 188978103, 741005255, 528655152, 732130620, 177126748, 150536661, 389322891, 371114062, 65334618, 119004311}, {0, 0, 377, 0, 413351, 0, 536948224, 0, 164248716, 0, 186229290, 0, 389322891, 0, 351258337, 0, 144590622}, {0, 1, 610, 7953, 1174500, 29253160, 720246619, 124166811, 498190405, 764896039, 274787842, 513673802, 371114062, 351258337, 722065660, 236847118, 451896972}, {0, 0, 987, 0, 3335651, 0, 704300462, 0, 200052235, 0, 732073997, 0, 65334618, 0, 236847118, 0, 974417347}, {0, 1, 1597, 29681, 9475901, 366944287, 289288426, 708175999, 282756494, 416579196, 320338127, 881924366, 119004311, 144590622, 451896972, 974417347, 378503901} }; int n, m; int g[N], t[N]; vector<int> V; int main() { while(scanf("%d%d", &n, &m) != EOF) { int ans = 0; for(int mask = 0; mask < (1 << m - 1); mask++) { int op = 1; V.clear(); int last = 0; for(int j = 0; j < m - 1; j++) { if(mask >> j & 1) { V.push_back(j + 1 - last); last = j + 1; op = -op; } } V.push_back(m - last); for(int i = 1; i <= n; i++) { t[i] = 1; for(auto &b : V) { t[i] = 1LL * t[i] * f[i][b] % mod; } } g[1] = t[1]; for(int i = 2; i <= n; i++) { g[i] = t[i]; for(int j = 1; j < i; j++) { sub(g[i], 1LL * g[j] * t[i - j] % mod); } } if(op > 0) add(ans, g[n]); else sub(ans, g[n]); } printf("%d ", ans); } return 0; } /* */