一共4道题目，2个小时。

题目1 - 圆桌座位

$N$ 个人围坐一圈，有 $M$ 对朋友关系。
第 $i$ 对朋友关系是指，编号是 $a_i$ 的人和编号是 $b_i$ 的人是朋友。
现在要给他们安排座位，要求所有相邻的人不能是朋友。问共有多少种方案？

如果两个方案只有旋转角度不同，则我们将其视为一种方案。

数据范围

• $3 \le N \le 10$
• $0 \le M \le N(N-1)/2$
• $1 \le a_i \lt b_i \le N$
• $(a_i, b_i) \neq (a_j, b_j)$
• 所有输入均是整数

输入格式

$N \ M$
$a_1 \ b_1$
…
$a_M \ b_M$

输出格式

输出一个数，表示总方案数

样例1

输入：

4 1
1 2

输出：

2

样例2

输入：

10 5
1 2
3 4
5 6
7 8
9 10

输出：

112512

算法

(DFS) $O(n!)$

首先，为了避免旋转造成的重复计数问题，我们将编号是1的人固定在1号位置。

然后从2号位置开始，依次枚举每个位置放哪个人，注意只能放跟上一个人没有朋友关系的人。
枚举到最后一个人时，如果他跟编号是1的人不是朋友，说明方案合法，我们将方案数加一。

时间复杂度分析：第一个人位置固定，那么剩下的人总共有 $(N-1)!$ 种放法，所以时间复杂度是 $O(N!)$。$N$最大是10，所以方案最多有 326880种，计算量可以接受。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 11;

int n, m, ans;
bool g[N][N], st[N];

void dfs(int u, int last_id)
{
    if (u == n)
    {
        ans += !g[last_id][1];
        return;
    }
    for (int i = 1; i <= n; i ++ )
        if (!st[i] && !g[i][last_id])
        {
            st[i] = true;
            dfs(u + 1, i);
            st[i] = false;
        }
}

int main()
{
    cin >> n >> m;
    for (int i = 0, a, b; i < m; i ++ )
    {
        cin >> a >> b;
        g[a][b] = g[b][a] = true;
    }
    st[1] = true;
    dfs(1, 1);
    cout << ans << endl;
    return 0;
}

题目2 - 求区间和

给定 $N$ 个整数 $a_1, a_2, … a_N$。
然后给出 $Q$ 个询问，第 $j$ 个询问给出两个整数 $x_j, y_j$，请计算所有 $|a_k|$ 的和，满足 $x_j \le k \le y_j$。

数据范围

• $1 \le N \le 10^5$
• $-10^9 \le a_i \le 10^9(1 \le i \le N)$
• $1 \le Q \le 10^5$
• $1 \le x_j \le y_j \le N(1 \le j \le Q)$
• 所有输入均是整数

输入格式

$N$
$a_1$
…
$a_N$
$Q$
$x_1 \ y_1$
…
$x_Q \ y_Q$

输出格式

输出 $Q$ 个数，分别表示每个询问的答案。

样例

输入：

6
1
-2
3
-4
5
6
3
1 2
2 4
3 6

输出：

3
9
18

算法

(前缀和) $O(N + Q)$

因为所有询问都是求绝对值的和，所以我们先将所有数取绝对值。

然后预处理出原数组的前缀和，使得 $S_i = \sum_{k=1}^ia_k$。

则 $\sum_{k=x}^ya_k = S_y - S_{x-1}$。
所以对于每个询问，我们可以直接用两个前缀和做差得到区间和。

时间复杂度分析：初始化复杂度是 $O(N)$，每个询问的复杂度是 $O(1)$，共有 $Q$ 个询问，所以总时间复杂度是 $O(N + Q)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, M = 100010;

int n, m;
int a[N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> a[i], a[i] = abs(a[i]);
    cin >> m;
    for (int i = 1; i <= n; i ++ ) a[i] += a[i - 1];

    for (int i = 0; i < m; i ++ )
    {
        int x, y;
        cin >> x >> y;
        cout << a[y] - a[x - 1] << endl;
    }
    return 0;
}

题目3 - 最短距离

有 $N$ 个村庄，编号1到 $N$。村庄之间有 $M$ 条无向道路，第 $i$ 条道路连接村庄 $a_i$ 和村庄 $b_i$，长度是 $c_i$。
所有村庄都是连通的。
共有 $K$ 个村庄有商店，第 $j$ 个有商店的村庄编号是 $x_j$。
然后给出 $Q$ 个询问，第 $k$ 个询问给出一个村庄的编号 $y_k$，问该村庄距离最近的商店有多远？

数据范围

• $2 \le N \le 10^5$
• $N-1 \le M \le min(N(N-1)/2, 10^5)$
• $1 \le Q \le 10^5$

输入格式

$N \ M$
$a_1 \ b_1 \ c_1$
…
$a_M \ b_M \ c_M$
$K$
$x_1$
…
$x_K$
$Q$
$y_1$
…
$y_Q$

输出格式

对于每个询问，输出该询问的结果。

样例

输入：

7 7
1 2 5
1 4 3
2 3 2
2 5 1
3 6 7
5 6 8
6 7 6
3
7
5
4
7
1
2
3
4
5
6
7

输出：

3
1
3
0
0
6
0

算法

(最短路) $O(km)$

由于 $N$ 和 $Q$ 都是 $10^5$ 级别的，所以我们不可能对每个询问，都求一遍单源最短路，会超时。

我们可以建立一个虚拟起点 $S$，然后从 $S$ 向每个有商店的村庄连一条长度是0的边。
然后求一遍以 $S$ 为起点的单源最短路。
此时，对于每个询问 $y_k$，$y_k$ 到 $S$ 的最短距离，就是 $y_k$ 到所有商店的最短距离。
这是因为从 $S$ 到 $y_k$ 的每条路径，都必然先走到某个商店，且走过的路程是0，然后再走向 $y_k$，所以 $S$ 到 $y_k$ 的最短路，就是所有商店到 $y_k$ 的最短路。

时间复杂度分析：我们用 $SPFA$ 算法求单源最短路经，它的时间复杂度期望是 $O(km)$，其中 $k$ 是常数，最坏是 $O(nm)$，最坏情况很难达到。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010, M = 300010, INF = 1000000000;

int n, m;
int h[N], e[M], ne[M], v[M], idx;
int dist[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, v[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void spfa()
{
    queue<int> que;
    for (int i = 1; i <= n; i ++ ) dist[i] = INF;
    st[0] = true;
    que.push(0);
    while (que.size())
    {
        int t = que.front();
        que.pop();
        st[t] = false;
        for (int i = h[t]; i != -1; i = ne[i])
            if (dist[e[i]] > dist[t] + v[i])
            {
                dist[e[i]] = dist[t] + v[i];
                if (!st[e[i]])
                {
                    que.push(e[i]);
                    st[e[i]] = true;
                }
            }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    int K;
    cin >> K;
    for (int i = 0; i < K; i ++ )
    {
        int id;
        cin >> id;
        add(0, id, 0);
    }
    spfa();
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i ++ )
    {
        int id;
        cin >> id;
        cout << dist[id] << endl;
    }
    return 0;
}

题目4 - 设计密码

你现在需要设计一个密码 $S$，$S$ 需要满足：

• $S$ 的长度是 $N$；
• $S$ 只包含小写英文字母；
• $S$ 不包含子串 $T$；

例如：abc和abcde是abcde的子串，abd不是abcde的子串。

请问共有多少种不同的密码满足要求？
由于答案会非常大，请输出答案模 $10^9+7$ 的余数。

数据范围

• $1 \le N \le 50$
• $1 \le |T| \le N, |T| 是 T 的长度$
• $T$ 只包含小写英文字母

输入格式

$N$
$T$

输出格式

一个数，表示总方案数模 $10^9+7$。

样例1

输入：

2
a

输出：

625

样例2

输入：

4
cbc

输出：

456924

样例3

输入：

3
xy

输出：

17524

样例4

输入：

50
password

输出：

448890425

算法1

(动态规划+KMP) $O(N^3)$

首先我们用KMP求出 $T$ 的 $next$ 数组。

然后我们回忆利用 $next$ 数组在长文本中匹配模板串 $T$ 的过程：如果下一个字母不匹配，需要一直沿着next指针找：j = next[j]，直到下一个字符匹配或者next指针指向开头为止。

然后我们会发现，假设我们已经匹配完长文本的前 $i$ 个字母，则剩下部分的匹配过程，只跟next指针的位置有关，因此我们可以用二维数组来表示当前状态的方案数：
f[i][j]表示匹配完前 $i$ 个字母时，next指针在 $j$ 时的方案总数。
状态转移也很自然：对于每个状态f[i][j]，我们从'a'-'z'枚举下一个字母，然后求出对应的next指针，假设是 $u$，则将f[i][j]的方案总数累加到f[i+1][u]。

转移过程中需要注意，因为密码中不能存在 $T$，所以next指针要避免转移到 $T$ 的最后一个字母。

时间复杂度分析：用KMP求next数组的时间复杂度是 $O(N)$，动态规划的状态有 $N^2$ 个，状态转移的计算量是 $25N$，所以总时间复杂度是 $O(25N^3) = O(N^3)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>

using namespace std;

const int N = 55, MOD = 1000000007;

int n, m;
string T;
int f[N][N];
int nxt[N];

void kmp()
{
    m = T.size();
    T = ' ' + T;
    for (int i = 2, j = 0; i <= m; i ++ )
    {
        while (j && T[j + 1] != T[i]) j = nxt[j];
        if (T[j + 1] == T[i]) j ++ ;
        nxt[i] = j;
    }
}

int main()
{
    cin >> n >> T;
    kmp();

    f[0][0] = 1;
    for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < m; j ++ )
            for (char k = 'a'; k <= 'z'; k ++ )
            {
                int u = j;
                while (u && k != T[u + 1]) u = nxt[u];
                if (k == T[u + 1]) u ++;
                if (u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
            }
    }
    int res = 0;
    for (int i = 0; i < m; i ++ ) res = (res + f[n][i]) % MOD;
    cout << res << endl;
    return 0;
}

算法2

(动态规划)$O(N^2)$

感谢评论区同学提供的一个很优秀的做法！时间复杂度与字符集大小无关，只有 $O(N^2)$。

我们从后往前不断添加新字符。
状态表示：$f[i][j]$ 表示长度为 $i$，以 $T$ 的末尾 $j$ 个字符开头，且包含 $T$ 的字符串个数。
注意：$f[i][j]$ 并不以最大后缀分类，所以 $f[i][j]$ 和 $f[i][k], (j \neq k)$ 可能包含相同字符串。
所以所有包含 $T$ 的字符串都在 $f[n][0]$中，所以答案就是 $26^n - f[n][0]$。

状态转移：
令 $m$ 表示 $T$ 的长度。

• 如果 $i \lt m$，则 $f[i][j] = 0$；

• 如果 $i \ge m$：
  当 $j = 0$ 时，$f[i][j] = 26^{i - m} - f[i - 1][m - 1] + 26 \times f[i - 1][0]$。

  • $S_1$ 表示以 $T$ 开头，总长度为 $m$ 的字符串集合，$|S_1| = 26^{m-l}$;
  • $S_2$ 表示在 $f[m-1][0]$ 所对应字符串的开头拼上任意字母组成的集合，$|S_2| = 26 \times f[m-1][0]$;
  • $S_3$ 表示以 $T$ 开头，且除了开头，在其它地方也出现过 $T$ 的字符串集合，$|S_3| = f[m-1][l-1]$；
  • $S$ 表示 $f[m][0]$ 对应的字符串集合;

  则 $S_1 - S_3$ 表示以 $T$ 开头，且 $T$ 不出现在其它地方的字符串集合。$S_2$ 表示在其它地方出现 $T$ 的字符串集合，所以 $S = S_1 - S_3 + S_2$。
  当 $j \neq 0$ 时，

  • 首先 $f[i][j]$ 可以从 $f[i - 1][j - 1]$ 转移过来，直接在字符串前面加上 $T[-j]$ 即可；
  • 当 $T$ 的前 $j$ 个字符和后 $j$ 个字符匹配时，$f[i][j]$ 同时要加上以 $T$ 开头，但其它地方不包含 $T$ 的字符串数量。

时间复杂度分析：总共 $N^2$ 个状态，状态转移的复杂度是 $O(1)$，所以总共时间复杂度是 $O(N^2)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55, MOD = 1000000007;

int n, m;
int f[N][N];
bool ismatch[N];
int pow26[N];
string T;

int pow26f(int k)
{
    long long res = 1;
    while (k -- ) res = res * 26 % MOD;
    return (int)res;
}

bool match(int k)
{
    for (int i = 0, j = m - k; i < k; i ++ )
        if (T[i] != T[j])
            return false;
    return true;
}

int main()
{
    cin >> n >> T;
    m = T.size();

    for (int i = 0; i <= n; i ++ ) pow26[i] = pow26f(i);
    for (int i = 0; i <= n; i ++ ) ismatch[i] = match(i);

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < m; j ++ )
        {
            if (i < m) f[i][j] = 0;
            else
            {
                if (!j) f[i][j] = (int)((pow26[i - m] - f[i - 1][m - 1] + 26ll * f[i - 1][0]) % MOD);
                else
                {
                    f[i][j] = f[i - 1][j - 1];
                    if (ismatch[j])
                        f[i][j] = (pow26[i - m] - f[i - 1][j - 1]) % MOD;
                }
            }
        }

    cout << pow26[n] - f[n][0] << endl;
    return 0;
}