A. Alternating Sum

题目看上去像一道单位根反演，可是推着就感觉很麻烦，模数也不太好。

考虑把这个和式分为 \frac{n}{k} 段，那么可以发现每段的值呈一个等比数列，公比为 \frac{a^k}{b^k} 。然后就可以用求和公式算了。注意公比在模意义下等于 1 时要特判。

B. Destruction of a Tree

容易发现树的节点数为奇数时一定无解。若树的节点数为偶数则一定可以构造出一组解。

我们在销毁一个节点时要保证：

• 该节点当前的度数为偶数
• 销毁该节点后产生的所有连通分量的大小为偶数

可以 DFS 从下往上贪心构造。当找到一个点满足以上两个条件时，那么可以从该节点开始顺序销毁它子树内所有未销毁的点。证明不难。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=330000;
const int P=998244353;
int n, inv[MAXN];
struct BIT
{
    int s[MAXN];
    int lb(int x) { return x&-x; }
    void init()
    {
        for (int i=1; i<=n; i++) s[i]=1;
    }
    void mul(int x, int k)
    {
        while (x<=n)
        {
            s[x]=1ll*s[x]*k%P;
            x+=lb(x);
        }
    }
    int query(int x)
    {
        int r=1;
        while (x>0)
        {
            r=1ll*r*s[x]%P;
            x-=lb(x);
        }
        return r;
    }
} bit;
int fa[MAXN];
vector<int> son[MAXN];
int d[MAXN], h[MAXN], ans;
bool cmp(int a, int b)
{
    return h[a]<h[b];
}
void dfs(int u)
{
    ans=(ans+bit.query(d[u]-1))%P;
    for (int i=0; i<son[u].size(); i++)
    {
        bit.mul(h[son[u][i]], inv[i+1]);
        if (i+1<son[u].size())
            bit.mul(h[son[u][i+1]], i+1);
    }
    for (int i=0; i<son[u].size(); i++)
    {
        int v=son[u][i]; dfs(v);
        bit.mul(h[v], 1ll*(i+1)*inv[i+2]%P);
        if (i+1<son[u].size())
            bit.mul(h[son[u][i+1]], 1ll*inv[i+1]*(i+2)%P);
    }
    for (int i=0; i<son[u].size(); i++)
    {
        bit.mul(h[son[u][i]], i+2);
        if (i+1<son[u].size())
            bit.mul(h[son[u][i+1]], inv[i+2]);
    }
}
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    scanf("%d", &n);
    d[1]=1; h[1]=n;
    for (int i=2; i<=n; i++)
    {
        scanf("%d", &fa[i]);
        son[fa[i]].push_back(i);
        d[i]=d[fa[i]]+1; h[i]=n;
    }
    for (int i=n; i>=1; i--)
    {
        if (son[i].empty()) h[i]=d[i];
        h[fa[i]]=min(h[fa[i]], h[i]);
        sort(son[i].begin(), son[i].end(), cmp);
    }
    inv[1]=1;
    for (int i=2; i<=n; i++)
        inv[i]=1ll*(P-P/i)*inv[P%i]%P;
    bit.init(); ans=0; dfs(1);
    printf("%d\n", ans);
    return 0;
}

D. Frequency of String

设模式串的长度之和为 M ，那么这些串有 O(\sqrt M) 种不同的长度。又因为所以串都不相等，所以每个长度的串出现次数为 O(|s|) ，所有串的出现次数总和为 O(|s|\sqrt M) 。对模式串建立 AC 自动机，把主串放在上面跑并合理地打上标记，即可求出每个模式串的所以出现位置。然后不难求得答案。代码：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN=110000;
const int MAXS=26;
const int INF=1E9;
vector<int> righ[MAXN];
struct ACAutomaton
{
    struct Node
    {
        int nxt[MAXS], fail;
        vector<int> pos;
    } st[MAXN];
    int cnt, root;
    int que[MAXN];
    void init()
    {
        cnt=0; root=++cnt;
    }
    void insert(char* s, int d)
    {
        int p=root;
        for (int i=0; s[i]; i++)
        {
            int x=s[i]-'a';
            if (!st[p].nxt[x]) st[p].nxt[x]=++cnt;
            p=st[p].nxt[x];
        }
        st[p].pos.push_back(d);
    }
    void build()
    {
        int op=0, cl=0;
        que[cl++]=root;
        while (op<cl)
        {
            int p=que[op++];
            for (int i=0; i<MAXS; i++)
            {
                int q=st[p].nxt[i], t=st[p].fail;
                t=t?st[t].nxt[i]:root;
                if (q)
                {
                    st[q].fail=t, que[cl++]=q;
                    for (int x:st[t].pos) st[q].pos.push_back(x);
                }
                else st[p].nxt[i]=t;
            }
        }
    }
    void query(char* s)
    {
        int p=root;
        for (int i=0; s[i]; i++)
        {
            p=st[p].nxt[s[i]-'a'];
            for (int t:st[p].pos)
                righ[t].push_back(i);
        }
    }
} acam;
char s[MAXN], t[MAXN];
int c[MAXN], l[MAXN];
int main()
{
//  freopen("D.in", "r", stdin);
//  freopen("D.out", "w", stdout);
    int n;
    scanf("%s%d", s, &n);
    acam.init();
    for (int i=1; i<=n; i++)
    {
        scanf("%d%s", &c[i], t);
        l[i]=strlen(t);
        acam.insert(t, i);
    }
    acam.build();
    acam.query(s);
    for (int i=1; i<=n; i++)
    {
        int ans=INF;
        for (int j=0; j+c[i]-1<righ[i].size(); j++)
            ans=min(ans, righ[i][j+c[i]-1]-righ[i][j]);
        printf("%d\n", ans==INF?-1:ans+l[i]);
    }
    return 0;
}