日记

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

Counting Rhyme# Link to

我们设 $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# Link to

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include<bits/extc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n,k;
int dp[4005][4005],pw[4005];
signed main()
{
    cin >> n >> k;
    pw[0] = 1;
    for (int i = 1; i <= n; i++)
        pw[i] = pw[i - 1] * k % mod;
    dp[1][1] = k;
    int ans = 0;
    for (int i = 2; i <= n; i++)
    {
        int tmp = 0;
        dp[i - 1][0] = dp[i - 1][k];// 我不明白
        for (int j = k; j >= 1; j--)
        {
            if (j != k)
                tmp = (tmp + dp[i - 1][j]) % mod;
            dp[i][j] = (dp[i - 1][j - 1] * (k - j + 1) + tmp) % mod;
        }
        ans = (ans + dp[i][k] * pw[n - i]) % mod;
    }
    cout << ans;
    return 0;
}

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

Another MEX Problem# Link to

我们看到：异或？？！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)$。

后日谈 # Link to 后日谈

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

反正我会。