洛谷题单指南-状态压缩动态规划-P4484 [BJWC2018] 最长上升子序列
原题链接：https://www.luogu.com.cn/problem/P4484
题意解读：求n个数所有排列的LIS的数学期望，说人话就是，求1-n的数字的所有排列的LIS之和的平均值。
解题思路：
1、暴力法
暴力法没什么好说的，对于n，枚举数字1~n的全排列，对于每一个排列求LIS，最后加总，除以n!。
但是全排列的时间复杂度n!，LIS的时间复杂度最小nlogn，整体nn!logn，显然是不可接受的。
2、动态规划
动态规划的想法不错，问题是太难想，这里就有一种奇技淫巧！
对于数字1~n的一个排列a，设a[i]表示第i个数，设pre[i]表示前i个数中能形成LIS的最大值，设diff[i]=pre[i]-pre[i-1]也就是pre的差分；
举例：
a：2 1 3
pre: 1 1 2
diff 1 0 1
根据pre的定义，一定有pre[i] <= pre[i+1] <= pre[i] + 1，相邻两个pre要么相等要么相差1，于是diff必然是0和1的组合！！！
基于以上分析，任何一个排列都可以表示为diff这样一组0/1的状态，可以压缩成二进制整数，我们只需要统计所有这样的状态对应的排列的数量，
而这些diff状态相同的排列，都一定有相同的LIS，等于diff中1的数量。
因此，我们定义f[i][j]表示前i个数组成的排列中diff状态为j的方案数。
有了状态定义，再来看怎么进行状态转移？
对于n=1，排列为：1。
对于n=2，可以基于n=1的所有排列，将2插入到各个地方，2插到1前面就是：2 1,2插到1后面就是：1 2，有2种排列。
对于n=3，可以基于n-2是所有排列，将3插入到各个地方，
3插入2 1有三种方式，对应：3 2 1，2 3 1，2 1 3；
3插入1 2也有三种方式：对应3 1 2，1 3 2，1 2 3。
一共有6种排列。
这就给了我们一个启示，可以实现n从小到大的递推，将一个最大的数n插入到1~n-1的所有排列各个位置，可以通过diff状态枚举来遍历所有排列，然后插入各个位置也可以更新新的diff状态，从而实现状态转移。
在一个排列插入一个最大的数时，假设插入位置为k，则当前diff[k]一定变成1，因为以k结尾的LIS一定增加1个，k后面的第一个1如果存在，设其位置为pos，diff[pos]应该变成0，因为插入的最大数改变了pos前面的pre的大小。
举例：
a：2 1 3 pre：1 1 2 diff：1 0 1
现将4插入2 1之间，得到
a：2 4 1 3 pre：1 2 2 2 diff：1 1 0 0
可以看出，对于diff来说，就是在1 0之间插入了1，变成1 1 0 1，然后将最后的1置0，变成1 1 0 0
3、优化技巧
技巧1：由于diff数组的第一位永远是1，状态可以省一位，只需要n - 1位表示状态。
技巧2：如果直接定义f[N][1 << N - 1]，空间也是吃不消的，由于f[i][j]值依赖于f[i-1][…]，可以通过滚动数组优化第一维。
技巧3：设状态为j，要在第k位插入一个1，并将k后面第一个1置0，这样的操作可以这样实现。
int t = (j >> k) << (k + 1) | (1 << k) | j & ((1 << k) - 1)
以上代码在第k位插入一个1，其中(j >> k) << (k + 1)获取第k位以上的状态并空出第k位，(1 << k) 就是第k位的1，j & ((1 << k) - 1)是状态j在第k位以下的状态。
int up=lowbit((j>>k) << (k+1));
以上代码第k位插入1之后，找到k后面第一个1的位置。
t^=up;
以上代码将第k位之后第一个1置0。
技巧4：由于状态省了第一位，枚举插入位置时，会缺少在开头插入最新值的操作，需要单独处理，在一个排列开头插入最大数，diff的开头还是1，其余的数整体左移但是原来第一位的1变成0，因此状态从j转移到j << 1。
4、打表
基于以上代码写出来之后，可以将n = 1 ~ n = 28都运行一遍，得到所有的结果，实现打表。
打表代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 28, M = 1 << (N - 1), MOD = 998244353;
int f[2][M]; //f[i][j]表示前i个数，排列后diff数组状态是j的方案数，j不包含最低位的1
int ones[M]; //ones[i]表示二进制i中1的个数
int n;
int lowbit(int x)
{
return x & -x;
}
int qmi(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1) res = 1ll * res * a % MOD;
a = 1ll * a * a % MOD;
b = b >> 1;
}
return res;
}
int main()
{
for(int i = 1; i < M; i++) ones[i] = ones[i - lowbit(i)] + 1; //预计算
for(int n = 1; n <= 28; n++) //打表
{
memset(f, 0, sizeof(f));
f[1 % 2][0] = 1; //初始化，前1个数排列后diff状态为0的方案数是1
for(int i = 2; i <= n; i++) //枚举所有数字个数
{
fill(f[i % 2], f[i % 2] + (1 << (i - 2)), 0); //因为是滚动数组，需清空当前行
for(int j = 0; j < (1 << (i - 2)); j++) //枚举i-1个数字时排列的状态
{
f[i % 2][j << 1] = (f[i % 2][j << 1] + f[(i - 1) % 2][j]) % MOD; //当将最新的数字插入到排列的头部时，单独处理
for(int k = 0; k <= i - 2; k++) //枚举将最新数字插入到已排列的位置，对应到diff中
{
int t = (j >> k) << (k + 1) | (1 << k) | j & ((1 << k) - 1); //在第k位插入一个1
int up = lowbit((j >> k) << (k + 1)); //第k位插入1之后，找到k后面第一个1的位置
t ^= up; //将第k位之后第一个1置0
f[i % 2][t] = (f[i % 2][t] + f[(i - 1) % 2][j]) % MOD; //状态转移，累加方案数
}
}
}
int ans = 0;
for(int i = 0; i < (1 << (n - 1)); i++)
{
ans = (ans + 1ll * f[n % 2][i] * (ones[i] + 1)) % MOD; //累加所有排列的LIS之和
}
int fac = 1;
for(int i = 1; i <= n; i++) fac = 1ll * fac * i % MOD; //求n!
ans = 1ll * ans * qmi(fac, MOD - 2) % MOD; //除以n!模MOD，就是乘上n!模MOD的逆元，用费马小定理计算逆元
cout << ans << ","; //输出打表内容
}
return 0;
}
100分代码：
#include <bits/stdc++.h>
using namespace std;
int a[] = {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;
cin >> n;
cout << a[n - 1];
return 0;
}