AtCoder Beginner Contest 367

待补：ABC 367 G 题解 - spdarkle - 博客园 (cnblogs.com)

D.一个湖周围有 $N$ 个休息区。
这些休息区按顺时针顺序编号为 $1$ 、 $2$ 、……、 $N$ 。
从休息区 $i$ 顺时针走到休息区 $i+1$ 需要 $A_i$ 步。(其中休息区 $N+1$ 指的是休息区 $1$ ）。
从休息区 $s$ 顺时针走到休息区 $t$ （ $s \neq t$ ）所需的最小步数是 $M$ 的倍数。
求 $(s,t)$ 的可能对数。

Sol:注意只能顺时针，所以固定起点的时候，到达任何一个点的路程都是确定的。考虑破环成链，维护%mod意义下的前缀和一个map桶，像滑动窗口维护这个map。但要注意边界，因$a_{i}$表示的是一条边。

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = n + 1; i <= 2 * n; i++) a[i] = a[i - n];
    map<int, int> mp;
    for (int i = 1; i <= 2 * n; i++) a[i] += a[i - 1], a[i] %= m;
    int ans = 0;
    // int sum = 0;
    //for (int i = 0; i <= 2 * n; i++) cerr << a[i] << " ";
   // cerr << endl;
   // deb(0);
   // for (int i = 0; i <= n - 1; i++) cerr << a[i] << " ";
    //cerr << endl;

    for (int i = 0; i <= n - 1; i++) mp[a[i]]++;
   
    ans = mp[0]-1;
    //deb(ans,mp);
    for (int i = 1; i <= n - 1; i++) {
        //deb(i);
        //for (int j = i; j <= i + n - 1; j++) cerr << a[j] << " ";
        //cerr << endl;
        mp[a[i - 1]]--;
        if (mp[a[i - 1]] == 0)
            mp.erase(a[i - 1]);
        mp[a[i + n - 1]]++;
        ans += mp[a[i]]-1;
        //deb(ans,mp);
    }
    cout << ans << endl;
}

E:基环树倍增模板：

给你一个长度为 $N$ 的序列 $X$ ，其中每个元素都介于 $1$ 和 $N$ 之间（含），以及一个长度为 $N$ 的序列 $A$ 。
打印在 $A$ 上执行以下操作 $K$ 次的结果。

  • 用 $B$ 替换 $A$ ，使得 $B_i = A_{X_i}$ .

Sol:发现可以建图i向$x_{i}$连边。然后形成了内向基环树森林。线性dp做法的实现难度较大，倍增对于在环上走很多步非常有用。

int n, m;
int a[N];
int x[N];
int st[N][65];
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) st[i][0] = x[i];

    for (int j = 1; j <= 60; j++) {
        for (int i = 1; i <= n; i++) {
            st[i][j] = st[st[i][j - 1]][j - 1];
        }
    }
    for (int i = 1; i <= n; i++) {
        int pos = i;
        for (int j = 60; j >= 0; j--) {
            if ((m >> j) & 1)
                pos = st[pos][j];
        }
        cout << a[pos] << " ";
    }
}

F.

  • 序列哈希板子：考虑对于一个序列，如果我们发现每次关心的都是其排序后结果，这意味着我们不在乎出现位置。我们考虑维护值域大小为M的桶（string代替），如果是集合那么其实是个01字符串。如果是可重集合，那么字符串第i个位置有cnt[i],表示这个可重集合中i这个值出现了cnt[i]次。选择一个质数base，记第i个位置的哈希值贡献为$base \ ^{cnt[i]}$.

题意：给你长度为 $N$ 的正整数序列： $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$ .

您需要依次处理 $Q$ 个查询。 $i$ -th 查询的解释如下。

  • 给定正整数 $l_i,r_i,L_i,R_i$ 。如果可以重新排列子序列 $(A_{l_i},A_{l_i+1},\ldots,A_{r_i})$ 以匹配子序列 $(B_{L_i},B_{L_i+1},\ldots,B_{R_i})$ ，则打印 “是”，否则打印 “否”。
constexpr u64 P = u64(1E18) + 9;
//constexpr u64 P = 998244353;
using Z = ModInt64<P>;
int n, m;
int a[N];
int b[N];
Z hsa[N], hsb[N];
random_device rd;
mt19937_64 gen(rd());
static int findprime() {
    int n = gen() % 1000000 + 1e6;
    if (n % 2 == 0)
        n++;
    while (true) {
        bool ok = 1;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) {
                ok = 0;
                n += 2;
                break;
            }
        }
        if (ok)
            return n;
    }
}
Z pwn[N];
const ull base = findprime();
void solve() {
    cin >> n >> m;
    pwn[0] = (u64)1;
    for (int i = 1; i <= N - 2; i++) pwn[i] = (pwn[i - 1] * base);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) {
        hsa[i] = hsa[i - 1] + pwn[a[i]];
        hsb[i] = hsb[i - 1] + pwn[b[i]];
    }
    for (int i = 1; i <= m; i++) {
        int l1, l2, r1, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (hsa[r1] - hsa[l1 - 1] == hsb[r2] - hsb[l2 - 1])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
}