【BZOJ1879】[SDOI2009]Bill的挑战（动态规划）

时间：2023-03-10 01:38:07
【BZOJ1879】[SDOI2009]Bill的挑战（动态规划）

【BZOJ1879】[SDOI2009]Bill的挑战（动态规划）

题面

BZOJ

洛谷

题解

本来还想着容斥来着，这个数据范围直接暴力就好。设\(f[i][S]\)表示当前填到了第\(i\)位，和\(S\)这些串匹配上的方案数。暴力转移即可。

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define MOD 1000003

void add(int &x,int y){x+=y;if(x>=MOD)x-=MOD;}

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

int cnt[1<<15],n,S,K,f[55][1<<15];

char ch[20][55];

int main()

{

	int T=read();

	for(int i=1;i<1<<15;++i)cnt[i]=cnt[i>>1]+(i&1);

	while(T--)

	{

		n=read();K=read();S=(1<<n)-1;

		for(int i=0;i<n;++i)scanf("%s",ch[i]+1);

		int l=strlen(ch[0]+1);

		memset(f,0,sizeof(f));f[0][S]=1;

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

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

				if(f[i-1][j]&&cnt[j]>=K)

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

					{

						int t=0;

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

							if((j&(1<<l))&&(ch[l][i]=='?'||ch[l][i]==k+97))

								t|=1<<l;

						add(f[i][t],f[i-1][j]);

					}

		int ans=0;

		for(int i=0;i<=S;++i)if(cnt[i]==K)add(ans,f[l][i]);

		printf("%d\n",ans);

	}

	return 0;

}

相关文章