A – Even Substrings

很简单，扫描的时候如果所在数位为偶数位，向答案添加当前数位即可。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
char str[66000];
int main()
{
    int ans = 0, len;
    scanf("%d", &len), scanf("%s", str + 1);
    for (int i = 1; i <= len; i++)
        if (((str[i] - '0') & 1) == 0)
            ans += i;
    printf("%d", ans);
    return 0;
}

B – Chocolates

从后面往前扫描，取上一个值减一和限制的最小值即可（记得特判\(0\)的情况）。

// B.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = (int)2e5 + 2000;
int n, arr[MAX_N], trial[MAX_N];
ll check()
{
    memset(trial, 0x3f, sizeof(trial));
    ll acc = 0;
    for (int i = n; i >= 1; i--)
    {
        if (trial[i + 1] == 0)
        {
            trial[i] = 0;
            continue;
        }
        trial[i] = min(trial[i + 1] - 1, arr[i]);
        acc += trial[i];
    }
    return acc;
}
int main()
{
    ll l = 0, r = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]), r += arr[i];
    printf("%lld", check());
    return 0;
}

C – Edgy Trees

乍一看很难的题，其实很水。

考虑直接容斥掉，初始答案为\(n^k\)，在建树的时候忽略掉黑边，然后对于每一个连通块计算出贡献\(subtreeSiz^k\)，记得这个贡献是负的：

\[ans = n^k – \sum_{t \in subtree} t.size()^k\]

// C.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e5 + 2000, mod = 1e9 + 7;
int head[MAX_N], current, n, tmpx, tmpy, tmpz;
int subtreeSiz[MAX_N], totTree, k;
bool vis[MAX_N];
struct edge
{
    int to, nxt, color;
} edges[MAX_N];
void addpath(int src, int dst, int color)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    edges[current].color = color, head[src] = current++;
}
ll quick_pow(ll bas, ll tim)
{
    if (bas == 1)
        return 1;
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
void dfs(int u, int org, int fa)
{
    vis[u] = true;
    subtreeSiz[org]++;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            dfs(edges[i].to, org, u);
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    bool flag = false;
    for (int i = 1; i <= n - 1; i++)
    {
        scanf("%d%d%d", &tmpx, &tmpy, &tmpz);
        if (tmpz != 1)
            addpath(tmpx, tmpy, tmpz), addpath(tmpy, tmpx, tmpz);
        else
            flag = true;
    }
    if (!flag)
        printf("0"), exit(0);
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs(i, ++totTree, 0);
    ll ans = quick_pow(n, k);
    for (int i = 1; i <= totTree; i++)
        ans = (ans - quick_pow(subtreeSiz[i], k) + mod) % mod;
    printf("%lld", ans);
    return 0;
}

D – Steps to One

参考了这位巨佬的文章：cf1139D. Steps to One(dp)

首先考虑设计状态，设\(dp[i]\)为当\(gcd\)为\(i\)时将整个序列的\(gcd\)变成\(1\)的期望长度。这个状态可以搞出：

\[ dp[i] = \frac{ \sum_{j = 1}^i dp[gcd(i,j)]+1 }{m} \]

然后我们可以枚举\(k=gcd(i,j)\)：

\[ dp[i] = 1 + \frac{ \sum_{k = 1}^m dp[k]*f(i,k) }{m} \]

其中\(f(i,k)\)代表在\(j \in [1,m]\)区间内满足\(gcd(i,j)=k\)的\(j\)的个数，我们可以考虑进行预处理。注意到枚举时可能会枚举到\(i\)自己，所以提出来：

\[ (1-\frac{\lfloor \frac{m}{i} \rfloor}{m})dp[i] = 1 + \frac{\sum_{k=1}^{i-1} dp[k]*f(i,k)}{m} \]

我们现在来思考如何预处理\(f\)函数。首先，我们可以把初值都设置为\(f(i,k) = \lfloor \frac{m}{k} \rfloor\)，然后对于\(u>v,v|u\)的数对，\(f(i,v)-=f(i,u)\)进行容斥即可。

// D.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e5 + 200, mod = 1e9 + 7;
vector<int> facts[MAX_N], cnt[MAX_N];
ll m, dp[MAX_N], invm;
ll quick_pow(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1)
            ans = ans * bas % mod;
        bas = bas * bas % mod;
        tim >>= 1;
    }
    return ans;
}
int main()
{
    scanf("%lld", &m), invm = quick_pow(m, mod - 2);
    for (int i = 1; i <= m; i++)
        for (int j = i; j <= m; j += i)
            facts[j].push_back(i);
    for (int i = 1; i <= m; i++)
    {
        cnt[i].resize(facts[i].size() + 1);
        for (int j = facts[i].size() - 1; j != -1; j--)
        {
            cnt[i][j] = m / facts[i][j];
            int siz = facts[i].size();
            for (int k = j + 1; k < siz; k++)
                if (facts[i][k] % facts[i][j] == 0)
                    cnt[i][j] -= cnt[i][k];
        }
    }
    ll ans = 0;
    for (int i = 2; i <= m; i++)
    {
        int dom = m, tmp = 0;
        for (int j = 0; j < facts[i].size(); j++)
            if (facts[i][j] == i)
                dom -= cnt[i][j];
            else
                tmp = (tmp + cnt[i][j] * dp[facts[i][j]] + mod) % mod;
        dp[i] = (tmp + m + mod) % mod * quick_pow(dom, mod - 2) % mod;
    }
    for (int i = 1; i <= m; i++)
        ans = (ans + dp[i] + 1 + mod) % mod;
    printf("%lld", ans * invm % mod);
    return 0;
}