日记 - 伊埃斯的博客站

都半期了我怎么还那么菜！！！

Counting Rhyme↗

我们设 $fl_i$ 表示 $a$ 里是否有 $i$ 的因子， $dp_i$ 表示有几组 $\gcd(a_x,a_y) = i$ 。显然这两个东西都可以在 $O(n \ln n)$ 的复杂度内求解，那么最终的复杂度就是 $O(n \ln n)$ 。~~甚至还比 $O(n \log_2 n)$ 优。~~

Non-Intersecting Subpermutations↗

2024/5/14 做过。~~好臭的日期~~

我们设 $dp_{i,j}$ 表示在前 $i$ 个数里，第 $(i - j,i]$ 个数内没有重复的情况下的贡献。答案就是 $\sum\limits_{i = 1}^{n}dp_{i,k}$ 。

我们考虑如何转移。我们想两种情况：第 $i$ 位是否在 $dp_{i - 1,j - 1}$ 这不重复的 $j - 1$ 个里面。如果不在，那么就会增加 $dp_{i - 1,j - 1} \times (k - j + 1)$ 的贡献。如果在，我们考虑枚举这个数在哪里重复了，增加 $\sum\limits_{l = j}^{k - 1}dp_{i - 1,l}$ 的贡献。

放一下代码：

1
#include<bits/extc++.h>
2
#define int long long
3
using namespace std;
4
const int mod = 998244353;
5
int n,k;
6
int dp[4005][4005],pw[4005];
7
signed main()
8
{
9
    cin >> n >> k;
10
    pw[0] = 1;
11
    for (int i = 1; i <= n; i++)
12
        pw[i] = pw[i - 1] * k % mod;
13
    dp[1][1] = k;
14
    int ans = 0;
15
    for (int i = 2; i <= n; i++)
16
    {
17
        int tmp = 0;
18
        dp[i - 1][0] = dp[i - 1][k];// 我不明白
19
        for (int j = k; j >= 1; j--)
20
        {
21
            if (j != k)
22
                tmp = (tmp + dp[i - 1][j]) % mod;
23
            dp[i][j] = (dp[i - 1][j - 1] * (k - j + 1) + tmp) % mod;
24
        }
25
        ans = (ans + dp[i][k] * pw[n - i]) % mod;
26
    }
27
    cout << ans;
28
    return 0;
29
}

我不明白：为啥要 dp[i - 1][0] = dp[i - 1][k]？

Another MEX Problem↗

我们看到：异或？？！MEX？？！~~考虑不做~~。

这俩恶心扒拉的东西凑一起了，我们~~不做也得做~~。

看到异或，我们的最优性 dp 直接原地爆炸，考虑可行性 dp。我们发现， $5000$ 以下数再怎么也异或不出大于 $10000$ 的数，~~更适合可行性 dp 了~~。设 $dp_{i,j}$ 表示前 $i$ 个数能否异或出 $j$ 。考虑转移：枚举上一段的结尾 $k$ ，那么有 $dp_{i,j} \leftarrow dp_{k,j \oplus \operatorname{MEX}_{l = k + 1}^{i}a_l}$ 。但是这样有 $O(n^3)$ 的复杂度，显然不可行。

考虑优化：我们定义一种东西叫“好的区间”，其意义为：对于区间 $[l,r]$ ，不存在区间 $[l',r']$ 使得 $\operatorname{MEX}_{i = l}^{r}a_i = \operatorname{MEX}_{i = l'}^{r'}$ 。可以证明这种区间只有 $O(n)$ 个，~~然而我并不会~~。于是我们只用转移这些个好的区间，时间复杂度 $O(n^2)$ 。

后日谈

即使注定失败，你也会坚持下去吗？

反正我会。

Thanks for reading!

日记

周五 3月 28 2025

632 字 · 4 分钟

life 日记