[ZJOI2005]沼泽鳄鱼

今天继续攻集训队论文的我

题意

一张无向图,不超过 50 个点
起点 s 终点 t
一个单位时间移动一次
一些食人鱼作周期运动 长度不超过 4
人不能碰到食人鱼
时刻 u 到达终点 u <= 2e9

分析

引理

我们观察数据发现n十分的小,那么就可以直接用邻接矩阵
而且有一种矩阵叫矩阵乘法
对于一张(无向)图:G ,G[i][j] = 1 表示 i – > j 有一条边
那么我们想一想G^2表示的意义是什么:

G^{‘}[a][b] = \sum_{k=0}^{N}G[a][k] * G[k][b]

那么是不是就是表示走2步的时候 a->b的方案数,那么以此类推
k布的方案数就是G^k了!

此题分析

我们用 A_k 表示走k布的情况下的方案数
G_i表示在走第 i 布是的图的情况(0,1)表示
那么如果没有食人鱼的话就是:
A_k = G^k
G^u = G^{u-1} * G_k
那么如果有食人鱼的话就是
A_k = A_{k-1} * G_k
那么我们看见食人鱼的循环是2,3,4不等,但是lcm(2,3,4) = 12
也就是意味着 G_1 = G_{13} 这两张图是一样的
那么我们可以O(n^3) 预处理出add矩阵

add=\prod_{k=0}^{12} G_k \\
a=k/12,b=k\mod12

那么答案的矩阵就是:

final=add^a*\prod_{1}^bG_i记住矩阵乘法的左乘和右乘是不一样的

复杂度O(n^3log_2{q})

代码:

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 55
#define M 25
#define R register
using namespace std;

int n, m, s, t, K, x, y, Nfish, Pow_time, leftn, ff[N], att[N][10];

struct matrix
{
    int a[N][N];
    matrix()
    {
        memset(a, 0, sizeof a);
    }
} G[20], fuu, ans, fff;

inline matrix operator * (matrix x, matrix y)
{
    matrix z;
    for(R int i = 0; i < n; ++i)
        for(R int j = 0; j < n; ++j)
            for(R int k = 0; k < n; ++k)
            {
                z.a[i][j] += x.a[i][k] * y.a[k][j];
                if(z.a[i][j] > 10000) z.a[i][j] %= 10000;
            }
    return z;
}


inline matrix Pow(matrix now, int y)
{
    matrix res;
    for(R int i = 0; i < n; ++i) res.a[i][i] = 1;
    while(y)
    {
        if(y & 1) res = res * now;
        now = now * now;
        y >>= 1;
    }
    return res;
}

inline void init()
{
    for(R int i = 1; i <= 12; i++)
    {
        G[i] = fuu;
        for(R int j = 1; j <= Nfish; j++)
        {
            int to = att[j][((i + 1) % ff[j]) ? ((i + 1) % ff[j]) : ff[j]];
            for(R int k = 0; k < n; k++)
                G[i].a[k][to] = 0;
        }
    }
}

inline matrix solve()
{
    Pow_time = K / 12;
    leftn = K % 12;
    matrix ans, fff;
    for(R int i = 0; i < n; ++i) ans.a[i][i] = fff.a[i][i] = 1;
    for(R int i = 1; i <= 12; ++i) fff = fff * G[i];
    ans = ans * Pow(fff, Pow_time);
    for(R int i = 1; i <= leftn; ++i)
    {
        ans = ans * G[i];
    }
    return ans;
}

inline int read()
{
    int x=0;
    char c=getchar();
    bool flag=0;
    while(c<'0'||c>'9'){if(c=='-')flag=1;   c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return flag?-x:x;
}

int main()
{
    n = read(), m = read(), s = read(), t = read(), K = read();
    for(R int i = 1; i <= m; ++i)
    {
        x = read(), y = read();
        fuu.a[x][y] = fuu.a[y][x] = 1;
    }
    Nfish = read();
    for(R int i = 1; i <= Nfish; ++i)
    {
        ff[i] = read();
        for(int j = 1; j <= ff[i]; ++j)
            att[i][j] = read();
    }
    init();
    ans = solve();
    printf("%d\n", ans.a[s][t]);
    return 0;
}

3 Replies to “[ZJOI2005]沼泽鳄鱼”

  1. hey there and thank you for your info – I’ve definitely picked up something
    new from right here. I did however expertise several technical issues using this site, since I
    experienced to reload the site lots of times previous
    to I could get it to load correctly. I had been wondering if your hosting is OK?
    Not that I am complaining, but sluggish loading instances times will often affect
    your placement in google and could damage your high quality score if advertising and marketing with Adwords.
    Anyway I’m adding this RSS to my email and could look out for a lot more of your respective interesting
    content. Make sure you update this again soon.. https://kikipedia.win/wiki/Are-You-Smoking-Dirty-Medical-Marijuana

发表评论

电子邮件地址不会被公开。 必填项已用*标注