Tag Archives

42 Articles

OI

「Codeforces 666C」Codeword – 题解

Posted by kal0rona on

主要思路

就这?思博题。

总觉得做过啊。答案很显然跟字符无关,我们需要固定最左边的子序列,然后枚举最后一位,得出结论(子序列 \(T\)、目标串长 \(n\)):

\[ ans = \sum_{i = |T|}^n 25^{i – |T|} \times 26^{n – i} {i – 1 \choose k – 1} \]

考虑把 \(n\) 提出来:

\[ ans = 26^n \sum_{i = |T|}^n 25^{i – |T|} \times 26^{-i} {i – 1 \choose k – 1} \]

发现一个重要性质:\(\sum |T| \leq 10^5\),所以对于不同的 \(|T|\),最好情况下个数为 \(\Theta(\sqrt{n})\)。那么既然 \(n\) 可以被独立出来,那么最后复杂度就是 \(\Theta(|T|\sqrt{n})\)。

OI

「LibreOJ」#572. 「LibreOJ Round #11」Misaka Network 与求和 – 题解

Posted by kal0rona on

主要思路

先考虑莫比乌斯反演?

\[ \begin{aligned} ans &= \sum_{i = 1}^n \sum_{j = 1}^n f(\gcd(i, j))^k \\ &= \sum_{d = 1}^n f(d)^k \sum_{i = 1}^n \sum_{j = 1}^n [\gcd(i, j) = d] \end{aligned} \]

经典化简:

\[ \begin{aligned} ans &= \sum_{T = 1}^n \lfloor \frac{n}{T} \rfloor^2 \sum_{x|T} \mu(x) f(\frac{T}{x})^k \end{aligned} \]

我们可以对这个 \(\lfloor \frac{n}{T} \rfloor^2\) 进行整除分块,所以问题的重心转移到了求后面那个 Dirichlet 卷积的前缀和身上。

OI

P3589:[POI2015]KUR – 题解

Posted by kal0rona on

主要思路

乍一看很难直接做,我们考虑从那个长度为 \(m\) 的串开始搞,发现每个 \(01\) 都对应的是一个不等式条件:

\[ a(s + i) + b < p \]

其中在 \(m\) 串的位置中为 \(i\),在 \(S\) 中的位置为 \(s + i\)。列了这么多之后进行区间交,然后发现性质 \(\gcd(a, n) = 1\),代表 \(ai \bmod n\) 是一一对应的,所以我们求最后的值的个数只需要减去 \([n – m + 1, n – 1]\) 内符合条件的数即可。

代码

// P3589.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

int n, a, b, p, m, ltot;
char str[MAX_N];
pair<int, int> limits[MAX_N << 2];

void create(int l, int r)
{
    if (l <= r)
        limits[++ltot] = make_pair(l, r);
    else
        limits[++ltot] = make_pair(l, n - 1), limits[++ltot] = make_pair(0, r);
}

int main()
{
    scanf("%d%d%d%d%d%s", &n, &a, &b, &p, &m, str);
    int ans = 0;
    for (int i = 0; i < m; i++)
        if (str[i] == '0')
            create((p + n - 1LL * i * a % n) % n, (0LL + n - 1 - 1LL * i * a % n) % n);
        else
            create((n - 1LL * i * a % n) % n, (p + n - 1LL * i * a % n - 1) % n);
    for (int i = 1; i < m; i++)
        create((0LL + b + n - 1LL * a * i % n) % n, (0LL + b + n - 1LL * a * i % n) % n);
    sort(limits + 1, limits + 1 + ltot);
    int tmp = -1;
    for (int i = 1; i <= ltot; i++)
    {
        if (limits[i].first > tmp)
            ans += limits[i].first - tmp - 1, tmp = limits[i].second;
        else
            tmp = max(tmp, limits[i].second);
    }
    printf("%d\n", ans + n - 1 - tmp);
    return 0;
}