T0

想想昨天还在调侃NFLS的出题人非常喜欢搜索，结果今天打不出搜索的人竟是我自己（孤寡
今天实在是做的非常差，补的题应该也不算多，所以干脆把前期的历史遗留问题解决一下（就是把写完blog之后改出来的记录一下）
悲伤.jpg

D1T8

给出一个{1,2,3,…,n}的全集，从其中选取子集S，满足：子集大小|S|≤k，(至少选择一个数)∏u∈S,u是一个平方自由数(square-free integer)，即这个数的质因子幂指数均为1。求满足条件的子集数mod 1e9+7。

若n 阿申准备报名参加GT考试，准考证号为n位数 X1X2⋯Xn，他不希望准考证号上出现不吉利的数字。
他的不吉利数字 A1A2⋯Am有m位，不出现是指 X1X2⋯Xn中没有恰好一段等于 A1A2⋯Am，A1和X1可以为 0。

甚至都不需要AC自动机（喜。
就是一个KMP+DP。
但是DP需要矩阵快速幂优化。

#include <bits/stdc++.h>
using namespace std;
const int N = 25;
int n, m, mod, ne[N], a[N][N];
char str[N];
void mul(int c[][N], int a[][N], int b[][N]) {
    int t[N][N] = { 0 };
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < m; k++) t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % mod;
        }
    }
    memcpy(c, t, sizeof t);
}
int quick_power(int k) {
    int f[N][N] = { 1 };
    while (k) {
        if (k & 1)
            mul(f, f, a);
        mul(a, a, a);
        k >>= 1;
    }
    int res = 0;
    for (int i = 0; i < m; i++) res = (res + f[0][i]) % mod;
    return res;
}
int main() {
    scanf("%d%d%d%s", &n, &m, &mod, str + 1);
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && str[j + 1] != str[i]) j = ne[j];
        if (str[j + 1] == str[i])
            j++;
        ne[i] = j;
    }
    for (int i = 0; i < m; i++) {
        for (int j = '0'; j <= '9'; j++) {
            int k = i;
            while (k && str[k + 1] != j) k = ne[k];
            if (str[k + 1] == j)
                k++;
            if (k < m)
                a[i][k]++;
        }
    }
    printf("%d", quick_power(n));
    return 0;
}

D2T7

给出n个字符串，m次询问，每次询问给定n个字符串中两个字符串的前缀，求这两个前缀的最长公共后缀，使得这个公共后缀是n个字符串中某个串的前缀
为了不使输出过大，你只需把这个字符串按照如下生成的26进制数转成10 进制后mod(1e9+7)后输出：

AC自动机+倍增求LCA

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n;
int h[N], e[N << 1], ne[N << 1], idx;
int id[N], cnt;
int d[N], Size[N], top[N], par[N], son[N];
char s[N];
vector<int> path[N];
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void dfs1(int u) {
    Size[u] = 1;
    d[u] = d[par[u]] + 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        par[j] = u;
        dfs1(j);
        Size[u] += Size[j];
        if (!son[u] || Size[j] > Size[son[u]])
            son[u] = j;
    }
}
void dfs2(int u, int t) {
    top[u] = t;
    if (son[u])
        dfs2(son[u], t);
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j != son[u])
            dfs2(j, j);
    }
}
struct node {
    queue<int> q;
    int acsize, fail[N];
    int trie[N][27], res[N];
    void insert(char *s, int id) {
        int p = 0;
        path[id].push_back(0);
        for (int i = 0; s[i]; i++) {
            int ch = s[i] - 'a';
            if (!trie[p][ch]) {
                trie[p][ch] = ++acsize;
                res[trie[p][ch]] = (26LL * res[p] + ch) % mod;
            }
            path[id].push_back(trie[p][ch]);
            p = trie[p][ch];
        }
    }
    void build() {
        for (int i = 0; i < 26; i++) {
            if (trie[0][i])
                q.push(trie[0][i]);
        }
        while (q.size()) {
            int u = q.front();
            q.pop();
            add(fail[u], u);
            for (int i = 0; i < 26; i++) {
                if (!trie[u][i])
                    trie[u][i] = trie[fail[u]][i];
                else {
                    fail[trie[u][i]] = trie[fail[u]][i];
                    q.push(trie[u][i]);
                }
            }
        }
    }
} AC;
int lca(int a, int b) {
    while (top[a] != top[b]) {
        if (d[top[a]] >= d[top[b]])
            a = par[top[a]];
        else
            b = par[top[b]];
    }
    return d[a] < d[b] ? a : b;
}
int main() {
    memset(h, -1, sizeof h);
    int n, m;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        AC.insert(s, i);
    }
    AC.build();
    dfs1(0);
    dfs2(0, 0);
    scanf("%d", &m);
    while (m--) {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);
        int x = path[a][b], y = path[c][d];
        printf("%d\n", AC.res[lca(x, y)]);
    }
    return 0;
}