P5188题解

· · 题解

前言：

在写这道题的时候踩了一个大坑，题目要求要在第 T 分钟或以前回到 1 号店，而不是恰好在第 T 分钟。
虽然 yukimianyan 大佬的题解思路写的已经非常清楚了，但我觉得代码有一点看不懂，于是决定用相同的思路再写一篇。

科技：

矩阵乘法、快速幂

思路：

首先不考虑买食材的限制，设 dp_{x,y} 为第 y 秒在 x 号节点的方案数。
则有：

dp_{x,0}=[x=1]\\ dp_{x,1}=[(1,x,w)\in E]\\ dp_{x,y}=\sum_{(u,x,w)\in E}dp_{u,y-1}+dp_{u,y-2}(y>1) \end{cases}

而看到 N\le25,T\le10^9 的范围，就很容易想到矩阵快速幂。
首先一个 1\times(2n+1) 的矩阵 T_i 表示：

再设计用于转移的 $(2n+1)\times(2n+1)$ 的矩阵 $base$ （ $T_i=T_{i-1}\times base$ ）。 其中，对于前 $i(i\le n)$ 列，矩阵中 第 $i+n$ 行为 $1$ ，其余均为 $0$ ，用于更新 $dp_{x,i-1}$ 的值（改为原 $dp_{x,i}$ ）。 对于所有的边 $(u,v,w)\in E$ ，应将矩阵中的第 $u+n$ 行，第 $v+n$ 列标为 $1$ (用 $dp_{u,i-1}$ 更新 $dp_{v,i}$ )。 第 $2n+1$ 列的第 $n+1$ 行和第 $2n+1$ 行标为 $1$ ，其余为 $0$ （ $ans$ 加上 $dp_{1,i-1}$ ）。 但是我们发现，转移时并没有利用到 $dp_{u,i-2}$ ，肯定有问题（没有考虑到要买全食材）。 用容斥原理解决这个问题： 设 $F_S$ 表示只能买集合 $S$ 内物品（不能买 $S$ 以外的物品）且最终回到一方案总数，则答案为： $F_{\begin{Bmatrix}B,J,M,P\end{Bmatrix}} -F_{{\begin{Bmatrix}B,J,M\end{Bmatrix}}}-F_{{\begin{Bmatrix}B,J,P\end{Bmatrix}}}-F_{{\begin{Bmatrix}B,M,P\end{Bmatrix}}}-F_{{\begin{Bmatrix}J,M,P\end{Bmatrix}}} +F_{{\begin{Bmatrix}B,J\end{Bmatrix}}}+F_{{\begin{Bmatrix}B,M\end{Bmatrix}}}+F_{{\begin{Bmatrix}B,P\end{Bmatrix}}}+F_{{\begin{Bmatrix}J,M\end{Bmatrix}}}+F_{{\begin{Bmatrix}J,P\end{Bmatrix}}}+F_{{\begin{Bmatrix}M,P\end{Bmatrix}}} -F_{{\begin{Bmatrix}B\end{Bmatrix}}}-F_{{\begin{Bmatrix}J\end{Bmatrix}}}-F_{{\begin{Bmatrix}M\end{Bmatrix}}}-F_{{\begin{Bmatrix}P\end{Bmatrix}}} +F_\varnothing

枚举集合 S 。
则此时的 base 矩阵中，对于所有的边 (u,v,w)\in E\land w\subseteq S ，第 u 行第 v+n 列标为 1 。
最后由矩阵乘法的结合律可知：

F_S=T_1\times {base_S}^T

时间复杂度 O(2^k\times \log T \times N^3)

代码：

//建议定义新矩阵时将其数组无脑memset 防止出错
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 30,M = 510,mod = 5557;
int n,m,T,l,a,b,c,ans,bx[410];
string s;
struct edge{int u,v,w;} g[M];
struct matrix{int n,m,s[N << 1][N << 1];} bgn,base,tmp;
matrix operator *(matrix x,matrix y)
{
    matrix ret;
    ret.n = x.n,ret.m = y.m;
    memset(ret.s,0,sizeof(ret.s));
    for(int i = 1;i <= x.n;i++)
        for(int j = 1;j <= y.m;j++)
            for(int k = 1;k <= x.m;k++)
                ret.s[i][j] = (ret.s[i][j] + x.s[i][k] * y.s[k][j] % mod) % mod;
    return ret;
}
int popcount(int x)
{
    int ret = 0;
    for(int i = 1;i <= 8;i <<= 1) if(x & i) ret++;
    return ret;
}
int v()
{
    int ret = 0;
    l = s.length();
    for(int i = 0;i < l;i++) ret |= bx[s[i]];
    return ret;
}
void init(int s)
{
    memset(base.s,0,sizeof(base.s));
    base.s[n + 1][2 * n + 1] = base.s[2 * n + 1][2 * n + 1] = 1;
    for(int i = 1;i <= n;i++) base.s[i + n][i] = 1;
    for(int i = 1;i <= m;i++)
    {
        base.s[g[i].u + n][g[i].v + n] = 1;
        if((g[i].w & s) == g[i].w) base.s[g[i].u][g[i].v + n] = 1;
    }
}
matrix ksm(matrix x,int y)
{
    matrix ret;
    ret.n = ret.m = 2 * n;
    memset(ret.s,0,sizeof(ret.s));
    for(int i = 1;i <= 2 * n;i++) ret.s[i][i] = 1;
    while(y)
    {
        if(y & 1) ret = ret * x;
        x = x * x;
        y >>= 1;
    }
    return ret;
}
//BJMP
int main()
{
//  freopen("data.in","r",stdin);
    bx['B'] = 1,bx['J'] = 2,bx['M'] = 4,bx['P'] = 8;
    cin >> n >> m;
    for(int i = 1;i <= m;i++)
    {
        cin >> a >> b >> s;
        c = v();
        g[i] = (edge){a,b,c};
    }
    cin >> T;
   //bgn就是T1
    memset(bgn.s,0,sizeof(bgn.s));
    bgn.n = 1,bgn.m = base.n = base.m = 2 * n + 1;
    bgn.s[1][1] = 1;
    for(int i = 1;i <= m;i++) if(g[i].u == 1) bgn.s[1][g[i].v + n] = 1;
    for(int i = 15;i >= 0;i--)
    {
        init(i);
        tmp = bgn * ksm(base,T);
        a = tmp.s[1][n * 2 + 1];
        if(popcount(i) & 1) ans = (ans - a + mod) % mod;
        else ans = (ans + a) % mod;
    }
    cout << ans << endl;
    return 0;
}