[NOI2017] 蚯蚓排队 - NekoMio's Blog

题目描述蚯蚓幼儿园有nnn只蚯蚓。幼儿园园长神刀手为了管理方便，时常让这些蚯蚓们列队表演。

所有蚯蚓用从 1 到 n 的连续正整数编号。每只蚯蚓的长度可以用一个正整数表示，根据入园要求，所有蚯蚓的长度都不超过 6 。神刀手希望这些蚯蚓排成若干个队伍，初始时，每只蚯蚓各自排成一个仅有一只蚯蚓的队伍，该蚯蚓既在队首，也在队尾。

神刀手将会依次进行 m 次操作，每个操作都是以下三种操作中的一种：

给出 i 和 j ，令 i 号蚯蚓与 j 号蚯蚓所在的两个队伍合并为一个队伍，具体来说，令 j 号蚯蚓紧挨在 i 号蚯蚓之后，其余蚯蚓保持队伍的前后关系不变。给出 i ，令 i 号蚯蚓与紧挨其后的一只蚯蚓分离为两个队伍，具体来说，在分离之后， i 号蚯蚓在其中一个队伍的队尾，原本紧挨其后的那一只蚯蚓在另一个队伍的队首，其余蚯蚓保持队伍的前后关系不变。给出一个正整数 k 和一个长度至少为 k 的数字串 s ，对于 s 的每个长度为 k 的连续子串 t （这样的子串共有 ∣s∣−k+1 个，其中 ∣s∣|s|∣s∣ 为 s 的长度），定义函数 f(t) ，询问所有这些f(t)的乘积对 998244353 取模后的结果。其中f(t)的定义如下：对于当前的蚯蚓队伍，定义某个蚯蚓的向后 k 数字串为：从该蚯蚓出发，沿队伍的向后方向，寻找最近的 k 只蚯蚓（包括其自身），将这些蚯蚓的长度视作字符连接而成的数字串；如果这样找到的蚯蚓不足 k 只，则其没有向后k数字串。例如蚯蚓的队伍为 10 号蚯蚓在队首，其后是 22 号蚯蚓，其后是 3 号蚯蚓（为队尾），这些蚯蚓的长度分别为 4 、 5 、 6 ，则 10 号蚯蚓的向后 3 数字串为456， 22 号蚯蚓没有向后 3 数字串，但其向后 2 数字串为56，其向后 1 数字串为5。

而 f(t) 表示所有蚯蚓中，向后 k 数字串恰好为 t 的蚯蚓只数。输入格式从标准输入读入数据。

输入文件的第一行有两个正整数 n,m ，分别表示蚯蚓的只数与操作次数。

第二行包含 n 个不超过 6 的正整数，依次表示编号为 1,2,…,n的蚯蚓的长度。

!!!

不想粘题了#

好气

链接LOJ

题解#

哈希能过
但要注意一下

每合并一次就相当于增加了50^2种情况
合并和拆分是一样的
然后查询的时候硬跑就可以了


#include <cstdio>
#include <cstring>
using namespace std;
#define LL unsigned long long
const int N = 300010, M = 15000010, L = 20000010;
const LL P = 23333333, p = 1000007, mod = 998244353;
int head[P], next[L], cnt[L], E, Next[N], Pre[N], a[N];
LL w[L], Pow[60];
int n, m;
char str[L];
void Insert(LL x, int y)
{
    LL now = x % P;
    bool flag = 0;
    for (int i = head[now]; i; i = next[i])
        if (w[i] == x)
        {
            cnt[i] += y;
            flag = 1;
            break;
        }
    if (!flag)
    {
        next[++E] = head[now];
        head[now] = E;
        cnt[E] = 1;
        w[E] = x;
    }
}
int Query(LL x)
{
    LL now = x % P;
    for (int i = head[now]; i; i = next[i])
        if (w[i] == x)
            return cnt[i];
    return 0;
}
void Change(int x, int y)
{
    int now = x;
    for (int k = 1; k <= 50; k++)
    {
        int ret = now;
        LL Hash = a[now];
        for (int j = 1; j <= k; j++)
        {
            ret = Next[ret];
            Hash = Hash * p + a[ret];
        }
        for (int l = k + 1; l <= 50; l++)
        {
            Insert(Hash, y);
            ret = Next[ret];
            if (!ret)
                break;
            Hash = Hash * p + a[ret];
        }
        now = Pre[now];
        if (!now)
            break;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        Insert(a[i], 1);
    }
    Pow[0] = 1;
    for (int i = 1; i <= 50; i++)
    {
        Pow[i] = Pow[i - 1] * p;
    }
    int op;
    int x, y;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d", &op);
        if (op == 1)
        {
            scanf("%d%d", &x, &y);
            Next[x] = y;
            Pre[y] = x;
            Change(x, 1);
        }
        else if (op == 2)
        {
            scanf("%d", &x);
            Change(x, -1);
            Pre[Next[x]] = 0, Next[x] = 0;
        }
        else
        {
            scanf("%s", str + 1);
            scanf("%d", &x);
            LL ret = 0;
            for (int i = 1; i <= x; i++)
                ret = ret * p + str[i] - '0';
            LL ans = Query(ret);
            LL len = strlen(str + 1);
            for (int i = x + 1; i <= len; i++)
            {
                ret = ret - (str[i - x] - '0') * Pow[x - 1];
                ret = ret * p + (str[i] - '0');
                ans = ans * Query(ret) % mod;
            }
            printf("%lld\n", ans);
        }
    }
}