DP(状压进阶二)

写在前面: 这篇题目很有难度, 是我觉得dp里面较难的类型, 先贴一波大佬的博客

我是传送门

题意 : 给定$n\leq15$n≤15个长度相同的字符串(由小写字母和问好’?'组成) 求这n个字符串中的刚好K个串匹配的字符串T的个数(T仅由小写字母组成) (若两字符串互相匹配, 则有两字符串的长度相等, 且对于任意的$1\leq i\leq S_{x.length}, 满足\quad S_x[i]=T[i]\quad 或者 \quad S_x[i] = '?'$1≤i≤Sx.length​,满足Sx​[i]=T[i]或者Sx​[i]=′?′)

>> face <<

Strategy:先筛出对于表示的是第i位能否与a_z匹配的1n号串的状态match, 于是每次转移都可以根据match达到可行的状态

状态: dp[i][j]匹配到第i位, $1-n$1−n串的状态为j的方案数

目标: $(\sum_{i}^{count(i) =k} dp[n][i]) \%mod$(∑icount(i)=k​dp[n][i])%mod

边界: $dp[0][(1&lt;&lt;n)-1]=1$dp[0][(1<<n)−1]=1

合法判断: 只有方案数不是0的方案才能进行转移

转移方程: $dp[j + 1][i \&amp; match[j][ch - &#x27;a&#x27;]] += dp[j][i]$dp[j+1][i&match[j][ch−′a′]]+=dp[j][i]

attention: 先筛match

双倍经验:

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define _rev(i, a, b) for (int i = (a); i >= (b); --i)
#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rof(i, a, b) for (int i = (a); i > (b); --i)
#define ll long long
#define db double
#define oo 0x3f3f3f3f
#define eps 0.00001
#define all(x) x.begin(), x.end()
#define met(a, b) memset(a, b, sizeof(a))
#define what_is(x) cerr << #x << " is " << x << endl
#define lowbit(x) x &(-x)
using namespace std;
const int maxn = 1e5 + 5;
const int mod = 1e6 + 3;
deque<string> s(20);
int match[55][30], dp[55][1 << 15], n, k;
int main()
{

	int t;
	cin >> t;
	while (t--)
	{
		cin >> n >> k;
		met(match, 0);
		met(dp, 0);
		_rep(i, 1, n)
		{
			cin >> s[i];
		}
		int len = s[1].size();
		_rep(i, 0, len - 1)
		{
			for (char ch = 'a'; ch <= 'z'; ch++)
			{
				_rep(j, 1, n)
				{
					if (s[j][i] == '?' || s[j][i] == ch)
					{
						match[i][ch - 'a'] |= 1 << j - 1; //match[i][j]表示的是第i位能否与a~z匹配的1~n号串的状态
					}
				}
			}
		}
		dp[0][(1 << n) - 1] = 1;//边界
		_rep(j, 0, len - 1)
		{
			_rep(i, 0, (1 << n) - 1)
			{
				if (dp[j][i])
				{
					for (char ch = 'a'; ch <= 'z'; ch++)
					{
						dp[j + 1][i & match[j][ch - 'a']] += dp[j][i];
						dp[j + 1][i & match[j][ch - 'a']] %= mod;
					}
				}
			}
		}
		ll ans = 0;
		_rep(i, 1, (1 << n) - 1)
		{
			if (__builtin_popcount(i) == k)
			{
				ans += dp[len][i];
				ans %= mod;
			}
		}
		cout << ans << endl;
	}
}