「BZOJ 5161」最长上升子序列「状压DP」

落日映苍穹つ 2023-06-05 12:50 2阅读 0赞

**题意**

求一个\\(1\\sim n\\)的排列LIS的期望长度，\\(n\\leq 28\\)

**题解**

考虑朴素的LIS：\\(f\[i\] = min(f\[j\]) + 1\\)

记\\(mx\[i\]\\)为\\(f\\)的前缀最大值，那么可以得到一个性质\\(mx\[i + 1\] \\in \[mx\[i\], mx\[i\] + 1\]\\)

对\\(mx\\)数组进行差分，则差分数组只有\\(01\\)，可以状压

由于\\(mx\[1\] - mx\[0\]=1\\)，从第二位开始状压

然后考虑从\\(1\\sim i\\)的排列推到\\(1\\sim i+1\\)的排列，\\(1\\sim i\\)的差分数组为\\(S\\)。把i插入第\\(j\\)（\\(1\\sim i+1\\)）个数前面：

若\\(j=1\\)：新状态为\\(S << 1\\)，即\\(mx\[2\]\\)为\\(0\\)，而其余不改

若\\(j>1\\)：\\(mx\[1\]\\) 到 \\(mx\[j - 1\]\\)不变，\\(mx\[j\]\\)到\\(mx\[i\]\\)整体右移一位，新的\\(mx\[j\]\\)为1，但要把新的\\(mx\[j\]\\)后面第一个\\(1\\)删去（因为\\(j\\)处答案变大了，所以该点和新答案一样大，差分数组对应\\(0\\)）

注意实现的时候第\\(k\\)个位置对应\\(1<<(k-2)\\)

打表程序：

static int dp[2][134217728], ans;
        for(int n = 1; n <= 28; n ++) {
              memset(dp, 0, sizeof dp); 
              int r = 0; dp[0][0] = 1; ans = 0;
              for(int i = 1; i < n; i ++, r ^= 1) {
                  fill(dp[r ^ 1], dp[r ^ 1] + (1 << i), 0);
                  for(int j = 0; j < (1 << (i - 1)); j ++) if(dp[r][j]) {
                      upd(dp[r ^ 1][j << 1], dp[r][j]);
                      int la = -1;
                      for(int k = i + 1; k >= 2; k --) {
                          int t = j;
                          if(j >> (k - 2) & 1) la = k - 2;
                          if(~ la) t ^= 1 << la;
                          t = t >> (k - 2) << (k - 1) | ( 1 << (k - 2) ) | ( j & (( 1 << (k - 2) ) - 1) );
                          upd(dp[r ^ 1][t], dp[r][j]);
                      }
                  }
              }
              for(int i = 0; i < (1 << (n - 1)); i ++)
                  upd(ans, 1ll * dp[r][i] * (__builtin_popcount(i) + 1) % mo);
              int fac = 1;
              for(int i = 2; i <= n; i ++) fac = 1ll * fac * i % mo;
              printf("%d, ", 1ll * ans * qpow(fac, mo - 2) % mo);
        }

提交程序：

#include <cstdio>
    const int qwq[] = {1, 499122178, 2, 915057326, 540715694, 946945688, 
    422867403, 451091574, 317868537, 200489273, 976705134, 705376344, 662845575, 
    331522185, 228644314, 262819964, 686801362, 495111839, 947040129, 414835038, 
    696340671, 749077581, 301075008, 314644758, 102117126, 819818153, 273498600, 267588741};
    int main() {
        int n; scanf("%d", &n); printf("%d\n", qwq[n - 1]);
        return 0;
    }

转载于:https://www.cnblogs.com/hongzy/p/11331756.html