棋盘游戏【51nod1327】【DP+组合数学】既然弱小，就只顾变强就是了-

题目链接

  首先要先强调，排列A(0, 0) = 1，被这个卡了半天。

  然后讲一讲关于这道题的思路，一开始想的方向是先完美匹配之后再去找增广路，但是发现一点增广路可以确定的是被替换，但是不能确定的是方案数，于是，肯定就该利用dp思想来解决该问题了。

  开始想办法dp，首先，想到的是我们不能去用行来进行约束，因为行的话没有确切的约束条件，但是通过每一列最多放一个这则消息，我们可以试着从列来进行展开，我们假设表示到第i列时候，前面还有j个列是空的情况。

  在输入中的”l, r”表示前l个和后r个中，各自刚好放有一个，所以对于前l时候，到第l位的时候必须要保证有一个，所以我们可以记录，“pre[l]++;”这样的方法，也就是到这一位的时候必须约束上。

  所以，dp的部分转移方程就可以看出来了。

  当我们排掉左边部分的约束的时候，dp应该是：，因为现在到第i+1位的时候，i+1位也还是空位的，然后我们必须从这j+1位里面取出个，保证合法性。

  但是这时候还是没有对右边的约束，所以我们还需要考虑右边的约束条件。

  因为是从左到右，但是我们如果用上面记录约束点的方式，那么我们应该计算的是累加不合法的数量，保证到第M个的时候，累加不合法数量为0即可。

  所以，我们还需要控制右边的“不合法”的数量，这时候先加上，然后最后到第M列的时候统计“0不合法”的答案即可。

  假设表示到第i列的时候，有k个不合法的时候，那么有状态转移方程：这是只考虑后面的状态的时候，但是同时考虑左边的时候，我们还是需要乘上左边的贡献，所以我们需要分以下的状态考虑：

• 放左

因为放左的时候，不需要考虑右边的，直接累加不合法数量即可。

• 放右

因为在这里，左边的是直接要保证的，但是第i+1位又是去放右边的了，所以左边选j位来放了，然后第i+1位放的到底是中的哪一位呢，这份贡献也要乘上去。

• 放中

  算了前面两种贡献之后，还是少算了一种可能性，就是当还有很多空格的时候，我们可以放空格中，此时左边的和右边的都不会加了，而是直接加给空白格。所以我们还是需要知道这段区间的数量，可以直接计算。

直接考虑放在哪块空白格即可。

 #include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <bitset> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define Big_INF 0x3f3f3f3f3f3f3f3f #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r #define MP(a, b) make_pair(a, b) using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const ll mod = 1e9 + 7; const int maxN = 55, maxM = 205; int N, M, l[maxN], r[maxN], pre[maxM] = {0}, suff[maxM] = {0}, mid[maxM] = {0}; ll dp[maxM][maxM][maxN]; ll A[maxM][maxM], jc[maxM]; inline ll fast_mi(ll a, ll b = mod - 2LL) {     ll ans = 1;     while(b)     {         if(b & 1) ans = ans * a % mod;         a = a * a % mod;         b >>= 1;     }     return ans; } inline void init() {     jc[0] = jc[1] = 1; for(ll i = 2; i<=200; i++) jc[i] = jc[i - 1] * i % mod;     A[0][0] = 1;     for(int i=1; i<=200; i++)     {         A[i][0] = 1;         for(int j=1; j<=i; j++)         {             A[i][j] = jc[i] * fast_mi(jc[i - j]) % mod;         }     } } inline void MOOD(ll &x) { if(x >= mod) x %= mod; } int main() {     dp[0][0][0] = 1;     scanf("%d%d", &N, &M);     init();     for(int i=1; i<=N; i++)     {         scanf("%d%d", &l[i], &r[i]);         pre[l[i]]++;         suff[M - r[i] + 1]++;         for(int j=l[i] + 1; j<=M - r[i]; j++) mid[j]++;     }     for(int i=0; i<M; i++)  //pos i th     {         for(int j=0; j<=i; j++) //pre j         {             for(int k=0; k<=N; k++) //illege k             {                 if(dp[i][j][k])                 {                     //left                     if(j + 1 >= pre[i + 1])                         MOOD(dp[i + 1][j + 1 - pre[i + 1]][k + suff[i + 1]] += dp[i][j][k] * A[j + 1]
] % mod);                     //right                     if(j >= pre[i + 1] && k + suff[i + 1] >= 1)                         MOOD(dp[i + 1][j - pre[i + 1]][k + suff[i + 1] - 1] += dp[i][j][k] * A[j]
] % mod * (k + suff[i + 1]) % mod);                     //mid                     if(j >= pre[i + 1])                         MOOD(dp[i + 1][j - pre[i + 1]][k + suff[i + 1]] += dp[i][j][k] * A[j]
] % mod * mid[i + 1] % mod);                 }             }         }     }     ll ans = 0;     for(int i=0; i<=M; i++) ans = (ans + dp[M][i][0]) % mod;     printf("%lldn", ans);     return 0; }