ABC 214E Chain Contestant(状压计数)()

ABC 214E Chain Contestant(状压计数)

Chain Contestant

现在有十个比赛类型,从现在开始要进行N场比赛。N场比赛的类型通过一个字符串S给出,在S串中选择一个子序列S’,满足下列要求:在子序列S’中,不能出现非连续的两个相同比赛类型。

请问S串中有多少满足条件的子序列S’,答案对998244353取模。

思路:

首先我们可以知道,对一个比赛是可以选或者不选,但是选择一个比赛会受到前面的选择的约束。所以容易可以想到这是一个计数DP问题。我们注意到比赛只有10个类型,这其中必定有深意。本题中对转移的限制就是不能有类似1021的方案,考虑用一个状态来表示一个比赛有没有在前面被选过。思路至此,已经十分明朗,我们可以用\(f[i][j][k]\)表示在前 i 个字符串中,j 是选过的比赛的二进制表示,k 表示最后一次选的是什么。

对于第 i 个字符,我们可以从st上该位为1的状态,且末位为该字符的状态转移过来,也可以从st上该位不为1的状态,且末位字符不为该字符的状态转移过来。对于每个字符本来可以作为子序列的首字符,所以要把对应的状态的方案数++。

代码

通过滚动来节省空间。

const int mod = 998244353;

int n;
char str[1005];
ll f[2][1 << 10][10]; //滚动

int main()
{
    scanf("%d%s", &n, str + 1);
    int num = str[1] - 'A';
    int flag = 0;
    f[flag][1 << num][num] = 1;

    for(int i = 2; i <= n; i ++)
    {
        flag ^= 1;
        for(int st = 0; st < (1 << 10); st ++)
            for(int j = 0; j < 10; j ++)
                if(st >> j & 1)  
                    f[flag][st][j] = f[flag ^ 1][st][j];

        int x = str[i] - 'A';
        f[flag][1 << x][x] ++;
        for(int st = 0; st < (1 << 10); st ++) //当前态
        {
            if(!(st >> x & 1))   continue; //因为是转移后的状态,所以st中的第i位为1
            for(int j = 0; j < 10; j ++) //之前的状态。分类讨论转移。
            {
                if(j == x)  
                    f[flag][st][x] += f[flag ^ 1][st][j];
                else
                    f[flag][st][x] += f[flag ^ 1][st - (1 << x)][j];
                f[flag][st][x] %= mod;
            }
        }
    }

    ll res = 0;
    for(int st = 0; st < (1 << 10); st ++)
        for(int j = 0; j < 10; j ++)
            res += f[flag][st][j], res %= mod;
    printf("%lld\n", res);
}
————————

ABC 214E Chain Contestant(状压计数)

Chain Contestant

现在有十个比赛类型,从现在开始要进行N场比赛。N场比赛的类型通过一个字符串S给出,在S串中选择一个子序列S’,满足下列要求:在子序列S’中,不能出现非连续的两个相同比赛类型。

请问S串中有多少满足条件的子序列S’,答案对998244353取模。

思路:

首先我们可以知道,对一个比赛是可以选或者不选,但是选择一个比赛会受到前面的选择的约束。所以容易可以想到这是一个计数DP问题。我们注意到比赛只有10个类型,这其中必定有深意。本题中对转移的限制就是不能有类似1021的方案,考虑用一个状态来表示一个比赛有没有在前面被选过。思路至此,已经十分明朗,我们可以用\(f[i][j][k]\)表示在前 i 个字符串中,j 是选过的比赛的二进制表示,k 表示最后一次选的是什么。

对于第 i 个字符,我们可以从st上该位为1的状态,且末位为该字符的状态转移过来,也可以从st上该位不为1的状态,且末位字符不为该字符的状态转移过来。对于每个字符本来可以作为子序列的首字符,所以要把对应的状态的方案数++。

代码

通过滚动来节省空间。

const int mod = 998244353;

int n;
char str[1005];
ll f[2][1 << 10][10]; //滚动

int main()
{
    scanf("%d%s", &n, str + 1);
    int num = str[1] - 'A';
    int flag = 0;
    f[flag][1 << num][num] = 1;

    for(int i = 2; i <= n; i ++)
    {
        flag ^= 1;
        for(int st = 0; st < (1 << 10); st ++)
            for(int j = 0; j < 10; j ++)
                if(st >> j & 1)  
                    f[flag][st][j] = f[flag ^ 1][st][j];

        int x = str[i] - 'A';
        f[flag][1 << x][x] ++;
        for(int st = 0; st < (1 << 10); st ++) //当前态
        {
            if(!(st >> x & 1))   continue; //因为是转移后的状态,所以st中的第i位为1
            for(int j = 0; j < 10; j ++) //之前的状态。分类讨论转移。
            {
                if(j == x)  
                    f[flag][st][x] += f[flag ^ 1][st][j];
                else
                    f[flag][st][x] += f[flag ^ 1][st - (1 << x)][j];
                f[flag][st][x] %= mod;
            }
        }
    }

    ll res = 0;
    for(int st = 0; st < (1 << 10); st ++)
        for(int j = 0; j < 10; j ++)
            res += f[flag][st][j], res %= mod;
    printf("%lld\n", res);
}