题解 P4484 【[BJWC2018]最长上升子序列】
皎月半洒花
2018-07-22 21:57:14
十分感谢GXZ大佬的讲解，此处致以敬意！本蒟蒻对于部分不是很清楚的地方整理了一下，大家可以结合起来食用。
[$Address$](https://www.cnblogs.com/GXZlegend/p/8619335.html)
________________
那么这道题，作为一道显然不是那么可做的题，我们首先来讲一下如何骗分：$next\_permutation$枚举全排列，然后$nlogn$求一遍长度，最终复杂度大约维持在$O(n!\times nlogn)$的水平，看一眼数据规模，好像对于$n\leq 9$的数据，在你的常数小的情况下跑出来时没有什么问题的。
$emmmm$思考一下数据范围，能够用最暴力的方法骗到分的概率极其的低。
于是我们考虑$dp$是否可行。
因为事实上，我们可以看到从左向右推好像不是很可行，于是我们考虑，对于一个排列，我们把数从小到大插入到一个空的数列里面。
那么我们首先令一个$f_i$（~~放心跟程序没啥关系~~）表示，在当前已经确定的一个序列里面，从左至右第$i$个数的最长上升子序列长度。基于这个数组，我们再令$maxL_i$表示前缀最大值，即$$maxL_i = max\{f_1,f_2...,f_i\}$$那么对于这个$maxL$数组，显然有$$maxL_i \leq maxL_{i+1} \leq maxL_{i} +1$$
诶，看上去这个$maxL$数组更加友善一些，因为我们可以差分它。不妨设对其进行差分的数组为$dif$。
_____
回归正题，在我们把数从小到大插入的时候，对于$dif$数组会出现如此情况：
考虑在第$i$位和第$i+1$位之间插入了一个新的数，而因为我们是单调地插入的，所以新插入的这个数一定是当前序列的最大数。那么很显然的是，这个数的$maxL$一定是$maxL_i+1$，因此把$dif_{i+1}$改成$1$，而在$i$之后第一个比$base_i$大的数，记其位置为$pos$，则$dif_{pos}$值肯定也为$1$，但是当我们插入了这个新的数之后，由于在它之前刚刚插入了一个不应该加入$f_{pos}$,所以我们应当把$dif_{pos}$置成零。
那么很显然了，我们接下来要做的就是对$dif$数组进行状压$DP$。
那我们不妨令$dp_{i,j}$表示在一个$1$~$ i$的排列里，差分数组$dif$状态为$j$的方案数，那么答案就是$$ans=\frac{1}{n!}\sum_{i =0}^{2^{n-1}-1}{dp_{n,i} \times getlen(i)}$$
也就是$\sum$有$n$个数、状态为$i$的方案$\times$方案中的$LIS$的长度。
值得一提的是，由于我们状压了$dif$数组，所以每个方案中$LIS$的长度，就是该状态里$1$的个数。
~~嗯，状压DP就是好啊~~
呃，什么，你说状态转移方程？我感觉像这种只有两维的状压$DP$的方程不都是一个样的吗……
至于代码，有几个$Tricks$值得留意：
$1$、我们发现其实$dp$数组的第一维$i$是可以滚掉的，所以我们就滚掉它，因为实际上我们最后的状态数量达到了$2^{27}$空间承受不起啊！所以我们就要卡着上限开，并且依旧会爆空间$OTZ$
$2$、因为一定会有$$maxL_1 = maxL_0+1= 1$$所以我们可以少状压一次。
$3$、为了便于递推，我所枚举的状态以及一系列都是跟数组的定义规则相同，跟二进制的定义规则相反。
$4$、我们最后由于求的是期望，所以要乘上$n!$的逆元，费马小定理求即可。
$5$、注意是取反号而不是取非号.因为我们在状压的时候，全0也是状态的一部分，所以我们在从后往前枚举（为了便于计算后面将要被置成的0）时应该到-1停止而不是到0停止。
```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long
using namespace std ;
const ll mod = 998244353LL ;
ll dp[2][134217730], getlen[134217730] ;
ll Mx, N, i, j, k, ans, fac = 1, now, t, pos ;
inline ll lowbit(ll x){return x & (-x) ; }
inline ll my_pow(ll a, ll b){
ll res = 1 ;
while(b){
if(b & 1)res = (res * a) % mod ;
a = (a * a) % mod ;
b >>= 1 ;
}
return res ;
}
int main(){
cin >> N ; N -- ; dp[0][0] = 1 ; Mx = 1 << N ;
for(now = i = 1; i <= N ; now ^= 1, i ++){
fill(dp[now], dp[now] + (1 << i), 0) ;
for(j = 0; j < (1 << (i - 1)); j ++){
dp[now][j << 1] = (dp[now][j << 1] + dp[now ^ 1][j]) % mod, pos = -1 ;
for(k = i - 1; ~k ; k --){
t = ((j >> k) << (k + 1)) | (1 << k) | (j & ((1 << k) - 1)) ;//(j >> k) << (k + 1)是为了先清掉后面的几位所以不能简写成j << 1
if(j & (1 << k)) pos = k ;
if(~pos) t ^= (1 << (pos + 1)) ;
dp[now][t] = (dp[now][t] + dp[now ^ 1][j]) % mod ;
}
}
}
for(i = 1; i < Mx; i ++) getlen[i] = getlen[i - lowbit(i)] + 1 ;
for(i = 0; i < Mx; i ++) ans = ( ans + 1ll * dp[N & 1][i] * (getlen[i] + 1) ) % mod ;
for(i = 1; i <= N + 1 ; i ++) fac = (fac * i) % mod ;
ans = ans * my_pow(fac, mod - 2) % mod ;
cout << ans ;
return 0 ;
}
```
但是无论如何，写这样一个状压DP，只能得到76分，开$O2$的话可以得到80分，是因为最终时间复杂度为$O(2^n \times n^2)$，空间的话也是大的要死，放在普通的的状压DP里面
已经足够优秀了，但是由于这个题的数据达到了惊人的$2^{27}$，所以我们最终选择用更前卫的方式解决：
# 打表
嗯，于是这个题就结束了。其实这个题据说有更优秀的做法，需要用到杨氏矩阵等。而因为本蒟蒻在省队集训的时候走神了，所以并不会杨氏矩阵$OTZ$
最后再贴一下打表的代码吧：
```cpp
#include <cstdio>
#include <iostream>
int N ;
int List[50]={19260817, 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(){
std::cin >> N ;
std::cout << List[N] ;
return 0;
}
```