双倍经验：4388. [Ynoi2019 模拟赛] Yuno loves sqrt technology I

好像还有个离线数据加强版但是我忘了题号了。

题意：强制在线查询区间 [l, r] 的众数，$n \leq 4\times 10^4$，$m \leq 5\times 10^4$。由$a_i$范围知道要离散化一下，记录每个值出现位置为$idx[x] = \{pos_1, pos_2, ..., pos_k\}$，同时如果要$O(1)$查询$j$在第$L$块到第$R$块之间的出现次数，就可以用前缀和预处理。

接着枚举起点块$i$，维护计数数组cnt，从块$i

........................................................................

该题解待审

运用 Dilworth 定理，转化为求满足最长下降子序列长度不超过 $3$ 的排列数量。

考虑如何刻画排列，是一个非常经典的 trick，维护一个空序列，每次在末尾插入大小不超过序列长度加一的一个数 $x$，并将原来序列中的所有 $\ge x$ 的数加一，最后一定能得到一个排列。其实就是在实时维护相对排名。

这样做的一个好处是，对于长度为 $i$ 的所有最长下降子序列，我们只关注结尾值最大的一个位置，因为我们是从末尾插入，新加入的数可以接在前面任何一个数后面，所以长度相同的下降子序列，最后一个数越大能表示的限制越多。

设 $f_{i,j,k}$ 表示 $1\sim i$ 的排列，长度为 $2$ 的最长下降子序列末尾值最大排名为 $j$，长度为 $3$ 的最长下降子序列末尾值最大排名为 $k$，新加入末尾的数为 $l$，根据 $l\in(k+1,j),(j+1,i],[i+1,i+1]$ 的取值去朴素转移，可以 $O(n^4)$，就是现在提交记录里 TLE 80 的代码。

不难发现转移的三个部分可以看成对下一个阶段的 dp 数组做单点加，一列加，一行加，用二维差分可以优化到 $O(n^3)$，但是可能被卡常了。

#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, mod, dp[N][N][N], ans;
long long c[N][N]; 
void add(int x, int y, int X, int Y, int v) {
    c[x][y] += v;
    c[x][Y + 1] -= v;
    c[X + 1][y] -= v;
    c[X + 1][Y + 1] += v;
    return;
}
int main(){
    freopen("great.in", "r", stdin);
    freopen("great.out", "w", stdout);
    cin >> n >> mod;
    dp[0][0][0] = 1;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k <= i; k++) {
                if (!dp[i][j][k]) continue;
                (dp[i + 1][j][k] += dp[i][j][k]) %= mod;
                add(j + 1, k + 1, j + 1, j, dp[i][j][k]);
                add(j + 1, k, i, k, dp[i][j][k]);
            }
        }
        for (int j = 0 ; j <= i + 1; j++) {
            for (int k = 0; k <= i + 1; k++) {
                if (j) c[j][k] += c[j - 1][k];
                if (k) c[j][k] += c[j][k - 1];
                if (j && k) c[j][k] -= c[j - 1][k - 1];
                (dp[i + 1][j][k] += c[j][k] % mod) %= mod;
            }
        }
        for (int j = 0 ; j <= n; j++) {
            for (int k = 0; k <= n; k++) {
                c[j][k] = 0; 
            }
        }
    }
    for (int j = 0; j <= n; j++) {
        for (int k = 0; k <= n; k++) {
            (ans += dp[n][j][k]) %= mod;
        }
    }
    ans = (ans % mod + mod) % mod;
    cout << ans << '\n';
    return 0;
} 

我其实把ntt忘干净了，只是用它卷积了而已。

可以理解为补充：http://218.28.19.228:8081/cogs/solution/solpl.php?pl=pmxmNJgjk。

3126. 自然数拆分Lunatic版

首先考虑n是2000的正整数拆分，正常可以用完全背包的办法搞定，这里我们考虑另一种办法。我们维护当前的递减序列的时候，每次操作都可以是把这堆数垫一层或者对着结尾放一个 $1$，就是这样：

这里每个竖着的格子高度代表了我们维护递减序列的值，绿色1就代表整体加一，后面一个小格子2就是往末尾加上了一个1。

所以说我们可以记录 $dp_{i,j}$ 表示选了 $i$ 个数，然后和是 $j$，所以说我们转移式子就是 $dp_{i,j}=dp_{i,j-i}+dp_{i-1,j-1}$，分别对应两种情况。

时间复杂度 $O(n^2)$，于是我们解决了3126. 自然数拆分Lunatic版。注意要减一因为看样例可以发现不能保留只有一个数的情况。

HS的自然数拆分2

就是上面的问题把 $n$ 改成 $100000$，然后不能重复。

根据不能重复，我们发现选连续一堆数加起来，从最小的 $1$ 开始加不能到 $\sqrt n$ 个（根据等差数列求和公式）。

所以HS就告诉我们可以用根号分治了，就是先考虑不超过 $\sqrt n$ 的数让他们和为 $n$ 的方案数，可以做到 $O(n\sqrt n)$，然后剩下大于 $\sqrt n$ 的显然选的个数也是有限制的，用我们上面的办法也可以 $O(n\sqrt n)$。

话说不能重复怎么办呢？我们上面的1操作是不会让原本合法的变成不合法的，只有可能是连续加了两个 $1$ 进去才会，所以说我们每次执行2操作之前先执行1一次就可以了。

细节上我们做问题后半部分的时候，2操作每次就不是加一了，而是我们规定的分治界限 $b$。

合并答案就按照定义来就可以，我的写法是把后半部分 dp 的数组对于 $n-i$ 的和枚举个数加起来，然后用这玩意乘上前一个和为 $i$ 的。

于是解决了HS的自然数拆分2，写的时候注意一下模数太大longlong会爆炸。

HS的自然数拆分

首先考虑只有一个数的情况。

相比于上一个问题，其实就是可以重复了。前半部分不说了，后半部分其实就是我们1和2操作分开做就可以了。

下面是HS晚上没讲的东西（相当于我刚刚一直在复述）

现在问题在怎么处理出每个的答案，发现对于$k$这个数的答案就是$\sum_{i=0}^k dp1_{i} \times sumdp2_{k-i}$，这里 $dp1$ 是我们前一半处理的，$sumdp2$ 是对于一个固定和的所有选数个数情况的和，这就是一个卷积的形式，直接跑ntt即可，$998244353$的原根是$3$。

怎么还要写简单的多重背包，我不是明天期末考吗。

HS：这题考察基本功（诶自然数拆分怎么做我看看）。

一个基础的观察：对于物品 $i$，当 $i\ge\sqrt{n}$ 时物品不可能取完，所以这部分是一个完全背包。

问题分成了两部分，设 $B=\lceil\sqrt{n}\rceil$，令 $F_i$ 表示只用 $1\sim B$ 这些物品体积为 $i$ 的方案数，$G_i$ 表示只用 $B+1\sim n$ 这些物品体积为 $i$ 的方案数，最后对 $F,G$ 卷一下即可。

对于 $F_i$：就是一个裸的完全背包，单调队列可以 $O(n\sqrt{n})$，但因为计数背包是可以退的，所以直接记录前缀和就可以 $O(n\sqrt{n})$。

对于 $G_i$：选择的物品不超过 $\sqrt{n}$ 个，考虑设 $g_{i,j}$ 表示这部分选择 $i$ 个物品体积和为 $j$ 的方案数，为了避免记重强制选择的物品体积单调递减。

问题变成了对一个单调递减，和为 $j$，最小数超过 $\sqrt{n}$ 的序列计数。如何刻画单调递减，经典做法是维护一个空数列，每次全局加一，或者在末尾加入一个最小元素，因此可以得出转移式 $g_{i,j}=g_{i,j-i}+g_{i-1,j-B-1}$。状态数是 $O(n\sqrt{n})$，转移是 $O(1)$ 的。

综上，在 $O(n\sqrt{n})$ 的时间复杂度内解决了本题。