P3758 [TJOI2017]可乐

先考虑DP，$f(i, j)$ 表示从 $i$ 到 $j$ 的方案数，则转移为 $f(i, j) = \displaystyle \sum _ {(i, k) \in E \wedge (k, j) \in E} f(i, k) *f(k, j)$ ，于是联想到了矩阵乘法。考虑如何处理自爆和停在原地操作。停在原地则添加一条自环即可，自爆则新加一个节点，每个点向该点添加一条边，而该点没有除自环外的其他边，则可以表示自爆的情况。

查看代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 31, mod = 2017;
int n, m, t, A[N][N], B[N][N], C[N][N];
int main()
{
    cin >> n >> m;
    for (int i = 0; i <= n; i++)
        A[i][i] = 1;
    for (int i = 1, a, b; i <= m; i++)
    {
        cin >> a >> b;
        B[a][b] = B[b][a] = 1;
    }
    for (int i = 0; i <= n; i++)
        B[i][i] = 1;
    for (int i = 1; i <= n; i++)
        B[i][0] = 1;
    cin >> t;
    while (t)
    {
        if (t & 1)
        {
            memset(C, 0, sizeof C);
            for (int i = 0; i <= n; i++)
                for (int j = 0; j <= n; j++)
                    for (int k = 0; k <= n; k++)
                        C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % mod) % mod;
            memcpy(A, C, sizeof A);
        }
        memset(C, 0, sizeof C);
        for (int i = 0; i <= n; i++)
            for (int j = 0; j <= n; j++)
                for (int k = 0; k <= n; k++)
                    C[i][j] = (C[i][j] + (B[i][k] * B[k][j]) % mod) % mod;
        memcpy(B, C, sizeof B);
        t >>= 1;
    }
    int res = 0;
    for (int i = 0; i <= n; i++)
        res = (res + A[1][i]) % mod;
    cout << res;
    return 0;
}