字符串练手题，不算太难。用字符串 $t$ 代指询问的串 $w$。

首先仔细琢磨一下，发现 $kq\le 10^5$，这启发对 $k$ 进行阈值分治，设阈值为 $B$。

对于 $k\ge B$，发现 $q$ 比较小，考虑对于每个询问，直接枚举所有 $i\in[a,b]$ 的 $[l_i,r_i]$ 来计算答案，对 $s$ 建立 SAM，并让 $t$ 的每个前缀 $t_i$ 跑出与 $s$ 子串匹配的最长后缀长度 $w_i$ 以及其对应的状态 $p_i$，若 $t_{l\sim r}$ 在 $s$ 中存在，则满足 $w_r\ge r-l+1$，对于其出现次数，只需要得到 $t_{l\sim r}$ 在 SAM 上对应的位置即可，预处理后缀树的倍增数组，跳到最后一个满足 $len_f\ge r-l+1$ 的 $p_r$ 的祖先 $f$，查询 $f$ 状态对应的 endpos 集合大小即可，预处理即可。

对于 $k<B$，注意到可以直接枚举 $t$ 的所有子串 $t_{l,r}$，并计算这个子串在 $s$ 的出现次数，同时计算区间 $[l,r]$ 在 $[a,b]$ 这个范围内出现多少次。对于前者，固定 $l$ 移动 $r$ 做匹配，匹配失败后面就直接退出，预处理后缀树的 endpos 集合大小即可计算次数，对于后者，拿 vector 存下每个区间在区间序列中出现的位置，然后二分查找计算出现次数即可。

理论复杂度可以做到 $O(n\sqrt{n\log n})$，两个部分都是，不知道能不能做到更优，实测取 $B=500$ 能过

本来还有 $30$ 分给多项式的，但是阻碍了伟大的 hxf 的 AK 之路，考虑到 CCF 不会出多项式，所以去掉了这一部分。

正难则反，考虑去算有那几步是不会产生贡献的，若第 $i$ 步不会产生贡献，则说明之前已经走到过这里一次了。

枚举第 $i$ 步所在的格子在 $t$ 步之前已经来到过这里了，设 $f_i$ 表示从一个位置出发，走 $i$ 步又回来，期间不经过这个位置的方案数。限制中间不经过是为了防止算重，求出 $f$ 后，答案为 $\sum_{i=1}^n\sum_{t=1}^if_t4^{n-t}$，不难发现这个式子和 $i$ 无关，继续化简为 $\sum_{t=1}^nf_t4^{n-t}(n-t+1)$。

问题是如何求出 $f$，考虑单步容斥，先求出 $g_i$ 表示从一个位置出发，走 $i$ 步又回来的方案数，则有 $f_i=g_i-\sum_{j=1}^{i}f_jg_{i-j}$。

对于 $g_i$，可以枚举竖直方向走了多少步，水平方向走了多少步，组合起来，通过组合恒等式可以证明当 $i$ 为偶数时，$g_i=(C_{i}^{i/2})^2$。另外一个方法是旋转坐标系 $45$ 度，无论上下左右都相当于在竖直和水平上都选择一个方向走一个单位长度，也能直接得到这个结论。

直接计算即可，瓶颈在于求 $f$，实际上可以用多项式优化，但是不是很文明所以去掉了。朴素实现是 $O(n^2)$，多项式是 $O(n\log n)$，听说存在 $O(n)$ 的做法。

双倍经验：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$往后逐块扩展$j$。每扩展一块，把该块所有数加入cnt，更新当前众数，记录到$p[i][j]$。

然后对于询问$[l, r]$，设$l$在块$bl$，$r$在块$br$。 如果同块或者相邻，那直接$O(2\sqrt{n})$枚举一下就完事了；如果跨块了，那就还是分成两小碎块和一大块处理。这时候发动我们的注意力：显然众数的候选区只有三个：1. 中间完整块的众数：$cand = p[bl+1][br-1]$ 2. 左零散中出现的每个数 3. 右零散中出现的每个数。这是为什么呢？显然中间完整快内其他蒲公英出现次数不可能比这几个众数还大，所以直接取中间众数，候选数最多$2B+1 \approx 401$个，每次$O(\log n)$，很舒服。

所以总复杂度预处理$O(n\sqrt{n})$，单次查询$O(\sqrt{n} \log n)$，总$O((n+m)\sqrt{n} \log n)$。很合理的一个式子。

运用 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;
}