2022 年牛客多校第九场签到题题解

A Car Show

题意：给定长度为 $nn$ 的序列 $\{a_i\}\backslash \{a\_i\backslash \}$，其中 $a_i\in [1,m]a\_i\; \backslash in\; [1,m]$，求有多少个连续子区间包含 $[1,m][1,m]$ 中每个数。$n,m\le 1\times 10^{5}n,\; m\backslash leq\; 1\backslash times\; 10^5$。

解法：使用双指针即可。时间复杂度 $\mathcal{O}(n)\backslash mathcal\; O(n)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int cnt[N + 5], a[N + 5];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    long long ans = 0;
    for (int i = 1; i <= n;i++)
        scanf("%d", &a[i]);
    int now = 0;
    for (int l = 1, r = 1; l <= n;l++)
    {
        while (r <= n && now < m)
        {
            if(!cnt[a[r]])
                now++;
            cnt[a[r]]++;
            r++;
        }
        if (now == m)
            ans += n - r + 2;
        cnt[a[l]]--;
        if (!cnt[a[l]])
            now--;
    }
    printf("%lld", ans);
    return 0;
}

B Two Frogs

题意：有一长度为 $nn$ 的数轴和 $22$ 个青蛙，初始均在 $11$ 号点，在第 $ii$ 号点两个青蛙都以等概率跳到 $[i+1,i+a_i][i+1,i+a\_i]$ 号点，问两青蛙以相同次数跳跃抵达 $nn$ 号点的概率。$n\le 8\times 10^{3}n\; \backslash leq\; 8\backslash times\; 10^3$。

解法：计算出单个青蛙的答案即可。设 $f_{i,j}f\_\{i,j\}$ 为在 $ii$ 号点，还需要跳跃 $jj$ 次抵达 $nn$ 号点的概率，则答案为 ${\displaystyle \sum _{i=1}^n{f}_{1,i}^2}\backslash displaystyle\; \backslash sum\_\{i=1\}^n\; f\_\{1,i\}^2$。其转移非常显然：${\displaystyle f_{i,j}=\frac{1}{a_i}\sum _{k=1}^{a_i}{f}_{i+k,j-1}}\backslash displaystyle\; f\_\{i,j\}=\backslash dfrac\{1\}\{a\_i\}\backslash sum\_\{k=1\}^\{a\_i\}f\_\{i+k,j-1\}$。使用后缀和优化即可，整体复杂度 $\mathcal{O}(n^2)\backslash mathcal\; O(n^2)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 8000;
const long long mod = 998244353;
long long power(long long a, long long x)
{
    long long ans = 1;
    while(x)
    {
        if (x & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ans;
}
int a[N + 5], f[N + 5][N + 5], suf[N + 5][N + 5];
long long inv[N + 5];
int main()
{
    int n;
    scanf("%d", &n);
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int i = 1; i <= n;i++)
        scanf("%d", &a[i]);
    f[n][0] = suf[n][0] = 1;
    for (int i = n - 1; i >= 1; i--)
    {
        suf[i][0] = suf[i + 1][0];
        for (int j = 1; j <= n; j++)
            f[i][j] = 1ll * (suf[i + 1][j - 1] - suf[i + a[i] + 1][j - 1] + mod) % mod * inv[a[i]] % mod,
            suf[i][j] = (suf[i + 1][j] + f[i][j]) % mod;
    }
    long long ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = (ans + 1ll * f[1][i] * f[1][i] % mod) % mod;
    printf("%lld", ans);
    return 0;
}