题目大意：

给出n和k，求从小于等于n的数中取出不超过k个，其乘积是无平方因子数的方案数。无平方因子数：不能被质数的平方整除。

题目分析：

10（枚举\(n\le8\)），40（简单状压\(n\le16\)），70（高级状压\(n\le30\)），100（正解状压n\le500,k\le500）。

对于前百分之70，由于\(n\le30\)，质数只有10个，直接状压水。

正解（状压dp+分组背包）：

注意到1~n中每个数含有的大于\(\sqrt{n}\)的质因数最多有1种，而\(\sqrt{n}\)内的质数只有8个，于是可以分别对待：

将1~n的数进行分组，含有大于\(\sqrt{n}\)的数分为一组，不含的单独成组，组内的每个元素用8位二进制表示该数含有的小于等于\(\sqrt{n}\)的质因子。

这样分组是因为小于等于\(\sqrt{n}\)的质数只有8个可以方便的进行状压dp，而含有大于\(\sqrt{n}\)质因子（只有1种）的数无法进行状压（时空不够），于是将其放在一个组内，dp时只取出该组中的一个数（保证大于\(\sqrt{n}\)的质因子不平方），从而降低时空。

code:

#include<bits/stdc++.h>

using namespace std;

const int N = 550, Mod = 1e9+7;

int T, n, k, dp[N][(1<<8)+50], state[N], val[N];

const int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19};

vector<int> vec[N];

int main(){

	scanf("%d", &T);

	while(T--){

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

		for(register int i = 1; i <= n; i++) vec[i].clear(), state[i] = 0;

		for(register int i = 1; i <= n; i++){

			val[i] = i;

			for(register int j = 0; j < 8; j++){

				if(val[i] % prime[j] == 0){

					val[i] /= prime[j];

					if(val[i] % prime[j] == 0){

						state[i] = -1;  //能够整除质数平方不合法

					}

					else state[i] |= (1 << j);

				}

			}

		}

		for(register int i = 1; i <= n; i++){

			if(state[i] == -1) continue;

			if(val[i] == 1){

				vec[i].push_back(i);  //不包含大于sqrtn的质因数

			}

			else vec[val[i]].push_back(i);  //大于等于sqrtn的质因数只可能有一个

		}

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

			for(register int j = 0; j < 256; j++)

				dp[i][j] = 0;

		dp[0][0] = 1;

		for(register int i = 1; i <= n; i++){

			int vecSze = vec[i].size();

			static int tmp[N];

			for(register int j = 0; j < vecSze; j++) tmp[j] = state[vec[i][j]];  //卡常操作

			for(register int l = k; l >= 1; l--){                //一组之中只能选择一个状态，l倒序

				for(register int j = 0; j < vecSze; j++){

					for(register int sta = (255^tmp[j]); ; sta = (255^tmp[j]) & (sta - 1)){  //枚举补集,减少一些赘余的状态

						dp[l][sta | tmp[j]] = (dp[l][sta | tmp[j]] + dp[l-1][sta]) % Mod;

						if(!sta) break;

					}

				}

			}

		}

		int ans = 0;

		for(register int i = 0; i < 256; i++){

			for(register int j = 1; j <= k; j++)

				ans = (ans + dp[j][i]) % Mod;

		}

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

	}

	return 0;

}

巴特西

NOIP模拟乘积 - 状压dp + 分组背包

题目大意：

题目分析：

code:

最新文章

热门文章

巴特西

NOIP模拟 乘积 - 状压dp + 分组背包

题目大意：

题目分析：

code:

最新文章

热门文章

NOIP模拟乘积 - 状压dp + 分组背包