序列划分（区间DP）

ruoye123456 / 2024-08-23 / 原文

题目描述
$n$个人，每个人手上有一个数$a_i$。

将这些人分成若干组，组没有编号，要求每组人手上的数字之和都是质数。

求合法的分组方案数。
输入
第一行一个正整数$T(1\leq T\leq 5)$，表示测试数据的组数。

每组数据第一行一个正整数$n(1\leq n\leq 15)$。

每组数据第二行$n$个正整数$a_1,a_2,\dots,a_n(1\leq a_i\leq 100)$。
输出
每组数据输出一行一个整数，即合法的分组方案数。
样例输入 Copy
1
3
3 2 5
样例输出 Copy
3

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 15;
int Lowbit[1<<N],Log2[1<<N],a[N],sum[1<<N];
ll f[1<<N];
bool st[2000];
void get_prime()
{ 
	st[0] = 0,st[1] = 0;
	for(int i=2;i<=2000;++i)
	{
	 	st[i] = 1;
	 	for(int j=2;j*j<=i;++j)
	 	{
	     	if(i%j==0) {st[i] = 0; break;}
	 	}
	}	
}
void solve()
{
	//对于集合S,设第一个被分出去的人i=lowbit(S),枚举含i的子集T
	//若T集合的和为质数则f[S]+=f[S-T]
	memset(f,0,sizeof f);
	f[0] = 1;
	int n;
	cin>>n;
	for(int i=0;i<n;++i) cin>>a[i];
	//需要预处理出每个状态的sum，否则会超时
	for(int i=0;i<(1<<n);++i)
	{
		int tmp = 0;
		for(int j=0;j<n;++j)
		{
			if(i>>j&1) tmp += a[j];
		}
		sum[i] = tmp;
	}
	for(int S=1;S<(1<<n);++S)
	{
		int i = Log2[Lowbit[S]];
		
		for(int T=S; T;T=(T-1)&S)
		{
			if(T>>i&1)
			{
				if(st[sum[T]]) f[S] += f[S-T];
			}
		}
	}
	cout<<f[(1<<n)-1]<<'\n';
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	for(int i=0;i<(1<<N);++i) Lowbit[i] = lowbit(i);
	Log2[0] = -1;
	for(int i=1;i<(1<<N);++i) Log2[i] = Log2[i/2]+1;
	get_prime();
	int T;
	cin>>T;
	while(T--)
	{
		solve();
	}
}