2022.10.27 整理

Problems

算是第一次线下做 S 组模拟题吧（其实并不知道具体难度是在 S 还是在省选，不过个人感觉就是个 S 组，虽然只有三个题），但是我就相当于一个旁观者，所以也没有测评代码，纯属自行估分。

感觉自己不会的东西还是非常多的，比如数据结构会但是想不到怎么用，想正解的能力还是太差了，如果碰上个简单的 T1（指能用 BF 干对的或是稍微预处理点就行的）可能还有救，然而概率太低了。

总之多写写结论题和思维题吧。

开题之后通读题面，断定三个题都不可做，感觉 T2 比较难就先放过去，开始写 T1。

研究 T1 的时候尝试加一些限制，确实在没有重复元素的情况下推出了正解并且愉快地爆碾了样例，但是再向有重复的元素扩展时没有成功，感觉单靠数学结论不大行了，就开始套 DS 去优化，然后乱搞了一顿，貌似能对（没写对拍）。

T1 是个 DS，但是我处理的方法非常笨，我将 $\mathcal{O}(n^2)$ 个区间全丢进去，这样导致最后四个数据是肯定没救的，如果写对了也就 60pts，极限分了。

T2 是个比较难的树上问题，是个树上差分，还是 DS，然而架不住菜，写了个 20pts 的 BF 就走了，不过这 20pts 给的是真舒适如果能再多点就好了。

事后证明，由于太过 BF，导致全 T……嘤嘤嘤……

T3 居然和 Stirling 数有关，我还在 solution 里瞅见了多项式……不过好像也就用到了证明性质，也不用手敲。T3 是单调栈然而自己过于菜导致没想到（想到了也不会），想了半天还是只能写个 10pts 的 BF……（这波靠 BF 活着了属于是），就死活优化不下去，后来想到了 DP（本场 contest 为数不多的和正解沾边的操作），然后试着写了写但还是挂掉了。

为什么我这么菜啊！

如果做法正确的话也就 90pts，不大行，任重而道远。

Solution

T1

思维题。

看一个区间包含多少个数有点麻烦，不妨转化为看一个数在多少个区间里。这样枚举可以节省时间，非常舒适。

令 $pre_i$ 表示 $a[i]$ 上一次出现的位置。数据范围有点大，我就不离散化（，我直接 map，简单又舒适。

对于重复的数的贡献，我们直接考虑最左边的一个，发现这个东西可以对前边 $i - pre_i$ 个区间产生贡献，也能对后边的 $n \times k - i + 1$ 个区间产生贡献。

因此总答案就是 :$\sum\limits^{k \times n}_{i = 1}{(i-pre_i)\times(k\times n-i+1)}$。

我们可以拆开算，发现右边的那一堆就是个等差数列，可以直接 $\mathcal{O}(1)$ 求出来，右边那一堆是不变的。

需要注意，当这个数是第一次出现的时候是需要特判一下的，因为此时它需要额外把前面所有的区间的贡献全部加上。

Code：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#define ll long long
#define int long long
#define INF 0x3f3f3f3f
using namespace std;

ll rd() {
    ll x = 0, w = 1;
    char c = getchar();

    while(c < '0' || c > '9') {
        if(c == '-') w = -1;
        c = getchar();
    }

    while(c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }

    return x * w;
}

const int N = 1e5 + 5;

const int mod = 1e9 + 7;
const ll inv2 = (mod + 1) >> 1;
int n; 
ll k, ans;
int a[N], b[N];
int pre[N];

map <int, int> mp;
bool fl[N];

ll calc(ll a, ll b, ll c) {
    return (a % mod + b % mod) % mod * c % mod *inv2 % mod;
}

signed main() {
    // freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
    n = rd(), k = rd();
    for(int i = 1; i <= n; ++i) {
        a[i] = rd();
        if(mp.count(a[i])) pre[i] = mp[a[i]];
        else fl[i] = true;
        mp[a[i]] = i;
    }
    
    for(int i = 1; i <= n; ++i)
        if(!pre[i] && mp[a[i]] != i) pre[i] = mp[a[i]];
        else if(fl[i] && !pre[i]) pre[i] = i;

    for(int i = 1; i <= n; ++i) {
        if(fl[i]) {
            ans = (ans % mod + ( 1ll * i % mod * 1ll * (n % mod * k % mod - i + 1) % mod) % mod) % mod;
            ans = (ans % mod + ((n + i - pre[i]) % mod * calc((n % mod * (k - 1) % mod - (i - 1) % mod) % mod, n - i + 1, k - 1) % mod) % mod) % mod;
        } else {
            ans = (ans % mod + (i - pre[i]) % mod * calc(((n % mod * k % mod - i + 1) % mod) % mod, n - i + 1, k) % mod) % mod;
        }
    }

    printf("%lld", ans);

    fclose(stdin);
    fclose(stdout);
    return 0;
}

/*
2 2
1 2
*/

附带对拍数据生成器：

#include <bits/stdc++.h>
using namespace std;

mt19937 rd(time(0));

int main() {
    uniform_int_distribution <int> rg1(1, 1e5);
    uniform_int_distribution <int> rg2(1, 1e9);

    int n = rg1(rd);
    cout << n << " " << rg1(rd) << endl;
    for(int i = 1; i <= n; ++i)
        cout << rg2(rd) << " ";
    return 0;
}

调试之路：

首先先跟丙戌年 dalao 学到了思路，顺便要到了 ACCode，然后开始钻研，然后开始写，接下来上去交了好几遍都是 30pts，气急败坏之下开始对拍，小数据都是 AC，大数据都爆炸。

最后经过多次研究，发现除法不能取模，被迫写成逆元，然后拍了遍大数据发现对了，接下来就 A 掉了。

T2

枚举 4 个点，得到 20 pts。

预处理出长度为 p，q 的路径，再判断。

判断路径相交用到 LCA，玩 tarjan 可以快点。

正着求有点难受，直接正难则反吧。

然后就不会了……

T3

dp，但是我听不懂……

我太菜了，见谅好吧，等我研究透 Solution 再说。（也许需要很长的时间……）