The Alphabet Sticker

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意：给你一串字符串，其中有一部分未知，用’?’表示。

现在定义一种合法的Sticker，比如”aabcc”，“ccccab”。即所有相同的字母要在一起才是合法的。现在请问对于给定的字符串，有多少种合法的结果。

比如：”aa??bb”合法的字符串有三种。

分别是“aaaabb” “aaabbb” ”aabbbb”.

‘?’表示的字符只能从已经给出的字符中选，所以”aaccbb”是不合法的。

由于最终结果很大，所以把结果对 1e9+7取模。

题目看懂之后思路就很明确了，一个组合问题。

分析一下：

1、相同字母需要在一起

2、只能从存在的字母中选。

显然的，‘?’只能从左边或者右边的字母中选取。

‘?’出现的情况有一下几种(打引号好累)：???xx xxx?? xx??xx xx?yy

第一种和第二种是一样的，因为出现在序列首/尾部。这两种情况只有1种。

第三种：只有一种，必须和x一样。

第四种：这个情况比较多，但是很容易感觉到会与‘?’的个数有关，来找下规律

aaa?bbb 长度 1 种数 2 aaaabbb aaabbbb

aaa??bbb 长度 2 种数 3 aaaaabbb aaaabbbb aaabbbbb

aaa???bbb 长度 3 种数 4 aaaaaabbb aaaaabbbb aaaabbbbb aaabbbbbb

规律很快就的出来了，种数 = 长度 + 1。

好了，所有‘?’出现的情况都分析过了，下面利用组合数学的知识，对于每一部分‘?’的种数应该乘起来求组合数。只需要在乘的过程中记得对mod取余，防止溢出就好了~

等下，是不是还忘记了一种情况。

我们默认认为数据都是合法的字符串，但是如果给你的就是一个不合法的字符串，那么这时候就应该输出0。

下面附上代码：

/*

 * Problem: A

 *    Date: 2014-7-20

 *  Author: Wuhen

*/

#include <map>

#include <list>

#include <queue>

#include <string>

#include <vector>

#include <cstdarg>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <iostream>

#include <algorithm>

#define LL long long

#define Clean(a) memset(a, 0, sizeof(a))

using namespace std;

bool vis[300];

const LL mod = 1e9+7;

LL deal(LL len, char l, char r)

{

    if (l == r) return 1;

    else return (len+1)%mod;

}

int main()

{

    LL T;

    cin >> T;

    while(T--)

    {

        string s;

        cin >> s;

        Clean(vis);

        LL all = 0;

        for (LL i = 0; i < s.size(); i++)

        {

            if (s[i] == '?') continue;

            if (vis[s[i]] == 0)

            {

                all += 1;

                vis[s[i]] = 1;

            }

            else

            {

                LL find = i-1;

                while(s[find] == '?' && find >= 0) find--;

                if (s[find] != s[i])

                {

                    all = 0;

                    break;

                }

            }

        }

        if (all == 0)

        {

            puts("0");

            continue;

        }

        LL res = 1;

        LL start = 0, stop = s.size() - 1;

        while(s[start] == '?' && start < s.size()) start++;

        while(s[stop] == '?' && stop >= 0) stop--;

        for (LL i = start; i <= stop; i++)

        {

            if (s[i] != '?') continue;

            char left = s[i-1];

            LL len = 0;

            while(s[i] == '?' && i <= stop)

            {

                len++;

                i++;

            }

            res *= deal(len, left, s[i]);

            res %= mod;

        }

        cout << res%mod << endl;

    }

    return 0;

}