题意

有N种不同的怪兽，标号为1到N。
　　每天晚上，所有的怪兽都会死去，当一只怪兽死去的时候，它会生出一只或者多只怪兽，因此怪兽的数量从来不会减少。
　　已知每种怪兽死去的时候能生出哪些种类的怪兽。
　　一开始你只有一只1类型的怪兽，你想要知道最终会有多少只怪兽，对1e9+7取模
　　如果有无穷多只，输出-1

思路

我的naive思路

用一下午做出一道题的感觉真是太舒服了。

看到此题便想到建一张有向图，a死掉之后生出b只c，那么就连一条a到c的权值为b的边。如果当前有a只b种类怪兽，，并且有一条边 $[b,c]=d$ ，那么死后就会出现 $a*d$ 只c怪兽。

因为懒，我开始写各种DFS，就是不想写tarjan（手动滑稽）。然后就各种不会特判，每次的思路都被自己插掉。于是终于缩了一波点，得到了一个DAG。

首先我们来考虑输出-1的情况。

一个强连通分量，必须是一个边权只有1的简单环，否则无限增加。证明有点不像证明，不管是边权大于1或者一个点连出多条边，都明显不行。
DAG上，只有出度为0的点在缩点前有大于1个点，否则输出-1。可以考虑下面这张图，前面的环生产怪兽，送到后面的环里循环。

怪兽繁殖（tarjan缩点）

好了，现在保证没有-1出现了，只需要在DAG上跑一个非常naive的DP就可以了。

整理完了感觉思路非常简单，但却反复修改思路改了一下午，有点菜。

LMOliver神仙的思路

假如是个定值，因为数据范围只有50，那么在50天之后，一定会达到这个定值；那么不管在哪个环上，经过 $Lcm(1, 2, 3, 4 ... 50)$ 天，肯定会回到原来情况。所以给邻接矩阵跑快速幂，多用几个mod，不然可能会被恶意卡掉。然后就A掉了？？？（雾）实在是太强了。

//代码比较凌乱，因为经过了多次恶意魔改
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<queue>
#define ll long long 
using namespace std;
const ll mod = 1e9+7;
const int N = 55;
int n, to[N][N], dfn[N], low[N], idx, stk[N], st, cnt;
int instk[N], col[N], snum, vis[N], add[N];
vector<int> scc[N];
ll sto[N][N], f[N];

void getEdge(int id, string s)
{
    int i = 0, len = s.size();
    while (i < len){
        while (s[i] < '0' || s[i] > '9' && i < len)
            ++i;
        int x = 0;
        while (s[i] >= '0' && s[i] <= '9' && i < len)
            x = x*10+s[i]-'0', ++i;
        ++to[id][x];
    }
}

void Tarjan(int u)
{
    dfn[u] = low[u] = ++ idx;
    instk[u] = 1;
    stk[++st] = u;
    for (int i = 1; i <= n; ++ i)
        if (to[u][i]){
            if (!dfn[i])
                Tarjan(i), low[u] = min(low[u], low[i]);
            else if (instk[i])
                low[u] = min(low[u], dfn[i]);
        }
    if (low[u] == dfn[u]){
        ++ snum;
        while (1){
            int v = stk[st--];
            instk[v] = 0;
            col[v] = snum;
            scc[snum].push_back(v);
            if (v == u) break;
        }
    }
}

void Dfs(int u, int c, int s)
{
    vis[u] = 1;
    for (int i = 1; i <= n; ++ i)
        if (to[u][i] && col[i] == c){
            if (to[u][i] > 1){
                cout << -1;
                exit(0);
            }
            if (!vis[i])
                Dfs(i, c, s);
            else if (s != i){
                cout << -1;
                exit(0);
            }
            else if (s == i){
                ++ cnt;
                if (cnt > 1){
                    cout << -1;
                    exit(0);
                }
            }
        }
}

ll Dfs1(int u)
{
    if (f[u] != -1) return f[u];
    f[u] = add[u];
    bool fl = 0;
    for (int i = 1; i <= snum; ++ i)
        if (sto[u][i])
            fl = 1, f[u] = (f[u]+sto[u][i]*Dfs1(i))%mod;
    if (fl && add[u]){
        cout << -1;
        exit(0);
    }
    return f[u];
}

int main()
{
    cin >> n;
    string s;
    getline(cin, s);
    memset(to, 0, sizeof(to));
    for (int i = 1; i <= n; ++ i){
        getline(cin, s);
        getEdge(i, s);
    }
    memset(dfn, 0, sizeof(dfn));
    memset(col, 0, sizeof(col));
    idx = st = snum = 0;
    Tarjan(1);
    for (int i = 1; i <= snum; ++ i){
        memset(vis, 0, sizeof(vis));
        cnt = 0;
        Dfs(scc[i][0], i, scc[i][0]);
    }
    memset(sto, 0, sizeof(sto));
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= n; ++ j)
            if (to[i][j] && col[i] && col[j]){
                if (col[i] != col[j])
                    (sto[col[i]][col[j]] += to[i][j]) %= mod;
                else
                    add[col[i]] = 1;
            }
    memset(f, -1, sizeof(f));
    cout << Dfs1(col[1]) << endl;
    return 0;
}

偷偷%LMOliver

怪兽繁殖（tarjan缩点）

题意

思路

我的naive思路

LMOliver神仙的思路

相关推荐