本文主要是介绍NOIP模拟（10.24）T2 乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
乘积
题目背景：
分析：状压DP
首先我们来看看70% 的数据，比较显然的我们可以状压一发，30以内只有10个质因数，首先对于每一个数判断是否有平方因子，若没有的话，我们定义num[i]表示i有哪些质因子，（二进制状压），然后定义dp[i][j][mask]表示当前枚举到i，已经选择了j个数，当前选择的质因数的状态为mask，状态转移很显然。
dp[i][j][c] à dp[i + 1][j + 1][c | num[i + 1]]((c & num[i + 1]) == 0) (选择i + 1)
dp[i][j][c] à dp[i + 1][j][c]（不选i + 1）
这样你就有70了，（然而可行状态少到打表，暴搜剪枝，枚举啥都能过······）
然后我们来看100的档，首先明确一点，在1 ~ n中的数，每一个数最多只会有一个大于sqrt(n)的质因子，那么我们可以对于每一个数，求出它大于等于sqrt(n)的质因子，然后按照这个质因子进行分组，即每一组只能选择一个，然后小于sqrt(n)的质因数最多只有8个，那么我们在70分状压上稍作改进，把每次枚举是否加入i改成，枚举加入i这个组中的哪一个元素，或者不加入这个组中的元素即可（出题人卡常卡到爆炸，各种常数优化······）
70状压
Source：
/*created by scarlyw
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <queue>const int prime[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
const int mod = 1000000000 + 7;
const int MAXN = 33;
const int MAXX = 10;int n, k, t, ans;
int dp[MAXN][MAXN][1 << MAXX | 1], num[MAXN];
bool unable[MAXN];inline void pre() {int cnt = 0;for (int i = 1; i <= 30; ++i) { for (int j = 0; j < MAXX; ++j) {if (i % (prime[j] * prime[j]) == 0) {unable[i] = true;break ;}if (i % prime[j] == 0) num[i] |= (1 << j);} }
}inline void add(int &x, int t) {x += t, (x >= mod) ? (x -= mod) : (0);
}inline void solve() {scanf("%d%d", &n, &k), ans = 0;memset(dp, 0, sizeof(dp));dp[0][0][0] = 1;for (int i = 0; i < n; ++i) {for (int j = 0; j <= k; ++j) for (int c = 0, s = (1 << MAXX); c < s; ++c) {if (dp[i][j][c] != 0) {if(!unable[i + 1] && (num[i + 1] & c) == 0)add(dp[i + 1][j + 1][c | num[i + 1]], dp[i][j][c]);add(dp[i + 1][j][c], dp[i][j][c]);}} }for (int i = 1; i <= k; ++i)for (int c = 0, s = (1 << MAXX); c < s; ++c)add(ans, dp[n][i][c]);std::cout << ans << '\n';
}int main() {
// freopen("mul.in", "r", stdin);
// freopen("mul.out", "w", stdout);scanf("%d", &t), pre();while (t--) solve();return 0;
}100状压
Source：
/*created by scarlyw
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <queue>const int prime[8] = {2, 3, 5, 7, 11, 13, 17, 19};
const int mod = 1000000000 + 7;
const int MAXN = 500 + 10;
const int MAXX = 8;int n, k, t, ans;
int dp[MAXN][1 << MAXX | 1], num[MAXN], a[MAXN];
std::vector<int> val[MAXN];
bool unable[MAXN];inline void pre() {for (int i = 1; i <= n; ++i) {a[i] = i;for (int j = 0; j < MAXX; ++j) {if (i % (prime[j] * prime[j]) == 0) {unable[i] = true;break ;}if (i % prime[j] == 0) a[i] /= prime[j], num[i] |= (1 << j);}if (!unable[i]) {if (a[i] == 1) val[i].push_back(i);else val[a[i]].push_back(i);}}
}inline void add(int &x, int t) {x += t, (x >= mod) ? (x -= mod) : (0);
}inline void solve() {scanf("%d%d", &n, &k), ans = 0;memset(dp, 0, sizeof(dp));for (int i = 1; i <= n; ++i) val[i].clear(), unable[i] = false;pre(), dp[0][0] = 1;for (int i = 1; i <= n; ++i)if (!unable[i] && val[i].size() != 0) {static int temp[MAXN];for (int j = val[i].size() - 1; j >= 0; --j) temp[j] = num[val[i][j]];for (int c = k - 1; c >= 0; --c) for (int j = val[i].size() - 1; j >= 0; --j)for (int s = (255 ^ temp[j]), t = s; ; s = ((s - 1) & t)) {add(dp[c + 1][s | temp[j]], dp[c][s]);if (s == 0) break ;}}for (int i = 1; i <= k; ++i)for (int c = 0, s = 256; c < s; ++c)add(ans, dp[i][c]);std::cout << ans << '\n';
}int main() {
// freopen("mul.in", "r", stdin);
// freopen("mul.out", "w", stdout);scanf("%d", &t);while (t--) solve();return 0;
}这篇关于NOIP模拟（10.24）T2 乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
