bzoj千题计划207：bzoj1879: [Sdoi2009]Bill的挑战

2021-07-02 01:49:31

http://www.lydsy.com/JudgeOnline/problem.php?id=1879

f[i][j] 表示匹配了i个字符，匹配字符串的状态为j的方案数

枚举下一个字符是什么

计算加上这个自字符之后新匹配到的状态s

f[i+1][s]+=f[i][j]

转移的时候判断如果f[i][j]==0，就不用枚举字符了

没有这个复杂度在6e8，TLE

其实可以预处理 g[i][j]表示已经匹配了长度为i，再加字符j 可以匹配到的状态

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=<<;

const int mod=;

char s[][];

int f[][N];

int bit[];

int count(int x)

{

    int sum=;

    while(x)

    {

        sum+=x&;

        x>>=;

    }

    return sum;

}

int main()

{

    bit[]=;

    for(int i=;i<=;++i) bit[i]=bit[i-]<<;

    int T;

    scanf("%d",&T);

    int n,t,m,len;

    int S,nj;

    int ans;

    while(T--)

    {

        scanf("%d%d",&n,&t);

        memset(f,,sizeof(f));

        m=;

        for(int i=;i<=n;++i)

        {

            scanf("%s",s[i]+);

            len=strlen(s[i]+);

            m=max(m,len);

        }

        S=bit[n];

        for(int i=;i<;++i)

        {

            nj=;

            for(int j=;j<=n;++j)

                if(s[j][]==i+'a' || s[j][]=='?') nj+=bit[j-];

            f[][nj]++;

        }

        for(int i=;i<m;++i)

            for(int j=;j<S;++j)

                if(f[i][j])

                    for(int k=;k<;++k)

                    {

                        nj=;

                        for(int l=;l<=n;++l)

                            if(j&bit[l-])

                                if(s[l][i+]==k+'a' || s[l][i+]=='?')

                                    nj+=bit[l-];

                        f[i+][nj]+=f[i][j];

                        f[i+][nj]-=f[i+][nj]>=mod ? mod : ;

                    }

        ans=;

        for(int i=;i<S;++i)

            if(count(i)==t)

            {

                ans+=f[m][i];

                ans-=ans>=mod ? mod : ;

            }

        cout<<ans<<'\n';

    }

}

1879: [Sdoi2009]Bill的挑战

Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 919 Solved: 477
[Submit][Status][Discuss]

Description

Input

本题包含多组数据。

第一行：一个整数T，表示数据的个数。

对于每组数据：

第一行：两个整数，N和K（含义如题目表述）。

接下来N行：每行一个字符串。

T ≤ 5，M ≤ 15，字符串长度≤ 50。

Output

如题

Sample Input

5
3 3
???r???
???????
???????
3 4
???????
?????a?
???????
3 3
???????
?a??j??
????aa?
3 2
a??????
???????
???????
3 2
???????
???a???
????a??

Sample Output

914852
0
0
871234
67018