题目描述

你是一个受欢迎的新游戏节目的参赛者，正在为大奖而努力！

有两个大按钮，一个是红色，另一个是黑色，你需要连续N次按动按钮，每次可任选其一按动。

你可以自由的制定你的按动顺序，但是有P个按动顺序序列被称为禁用开头，每个长度不大于N。

如果你的按动顺序在开始时就包含了禁用开头，那么你就不会赢得大奖。

当然，你的按动顺序序列可以包含一个或多个禁用开头，但是前提是它们不能出现在序列的开头。

如果一个长度为N的按动顺序序列在开头不包含任何禁用开头，那么这个序列就是一个获胜序列。

请问共有多少个不同的获胜序列？

样例

输入样例：
4
3 2
BBB
RB
5 1
R
4 3
R
B
RBRB
50 5
BRBRBBBRBRRRBBB
BRBRBRRRBRRRBRB
BBBRBBBRBRRRBBB
BRBRBRRRBRRRB
BRBRBBBRBBBRB
输出样例：
Case #1: 5
Case #2: 16
Case #3: 0
Case #4: 1125556309458944

算法1

(Trie树)

1. 使用Trie树的话，把所有的禁用的字符串P，都insert到Trie树中
2. 不需要判断前缀，只需要给加进去的P字符串的末尾加一个标记(is_end)即可。
3. dfs()函数就是用来计算出需要减掉多少个方案，直接对Trie树进行dfs就行。
4. 时间复杂度低很多，50W。

时间复杂度

$O(TPN)$
T表示测试数据的数量
P表示禁用的字符串前缀的个数
N表示字符串的最大长度

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 5010;

int n, p;
int idx, son[N][2];
bool is_end[N];

void insert(char s[])
{
    int r = 0;
    for(int i = 0; s[i]; i ++)
    {
        int u = s[i] == 'R' ? 0 : 1;
        if(!son[r][u]) son[r][u] = ++ idx;
        r = son[r][u];
    }

    is_end[r] = true;
}

LL dfs(int u, int k)
{
    if(is_end[u]) return (1ll << (n - k));

    LL ans = 0;
    for(int i = 0; i < 2; i ++)
        if(son[u][i])
            ans += dfs(son[u][i], k + 1);

    return ans;
}

int main()
{
    int T;
    cin >> T;

    for(int cases = 1; cases <= T; cases ++)
    {
        LL res = 0;
        memset(son, 0, sizeof son);
        memset(is_end, false,sizeof is_end);
        idx = 0;

        cin >> n >> p;
        while(p --)
        {
            char s[60];
            scanf("%s", s);
            insert(s);
        }

        res = (1ll << n) - dfs(0, 0);

        printf("Case #%d: %lld\n", cases, res);
    }
}

算法2

(哈希表)

1. 找到前缀对应的最后一个节点，将该节点的所有儿子删掉。
2. 如果统计要删除的儿子数量呢？假如字符串一共有n位，前缀有k位，后面就有(n - k)位，每一位都有2种选择，所以儿子的数量是$2^{n-k}$。
3. 最后我们的方案数就是用总数，删去，所有前缀的儿子数——
   $$2^n - \Sigma 2^{n - k_i} (i = 1, 2, …, P)$$
4. 会出现前缀有重复的情况，也就是 当一个节点在另一个节点的子树中的时候，就出现了重复 ，这样会导致多删。
5. 所以我们要先进行判重——查看一个点是否在另一个节点的子树上
6. 接下来则是进行过滤—— 如果a是b的前缀，则将b删掉
7. 过滤：

   • 将所有的禁用开头P排序，按照字典序，这样可以保证 如果重现了重复前缀，那么重复的前缀会出现在前面
   • 从前往后扫描，查看是否有前缀，有前缀就删掉；没有前缀就存储进 哈希表中
   • 如何判断是否有重复前缀？——暴力判断，假如字符串b是“RBR”，先判断“R”，再判断“RB”，再判断“RBR”

8. 最后进行 总数 - 前缀数
9. 代码中，要建立一个bool型变量exist，初值定为false。如果有前缀，就变成true。如果str[i]没出现过，就用2的n次方减str[i]，如果出现过就不用减了，不然会重复减。最后每次遍历完一个str[i]以后，不管有没有前缀，都要将它放到uss中，因为可能后面会出现str[i]的子节点。

时间复杂度

$O(TPN^2)$
$2.5 × 10^7$

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110;

typedef long long LL;

string str[N];
int n, p;


int main()
{
    int T;
    cin >> T;
    for(int cases = 1; cases <= T; cases ++)
    {
        cin >> n >> p;
        for(int i = 0; i < p; i ++) cin >> str[i];

        LL res = 1ll << n;
        unordered_set<string> uss;

        sort(str, str + p);
        for(int i = 0; i < p; i ++)
        {
            string a;
            bool exist = false;

            for(int j = 0; j < str[i].size(); j ++)
            {
                a += str[i][j];
                if(uss.count(a))
                {
                    exist = true;
                    break;
                }
            }

            if(!exist) res -= (1ll << (n - str[i].size()));
            uss.insert(str[i]);
        }

        printf("Case #%d: %lld\n", cases, res);
    }

    return 0;
}