【问题描述】
《集合论与图论》这门课程有一道作业题,要求同学们求出{$1, 2, 3, 4, 5$}的所有满足以 下条件的子集:若$x$在该子集中,则$2x$和$3x$不能在该子集中。同学们不喜欢这种具有枚举性质的题目,于是把它变成了以下问题:对于任意一个正整数$n\le100000$,如何求出{$1, 2,…, n$} 的满足上述约束条件的子集的个数(只需输出对$1,000,000,001$取模的结果),现在这个问题就交给你了。
【输入格式】
只有一行,其中有一个正整数$n$,$30%$的数据满足$n\le20$,$100%$的数据满足$n \le 100000$。
【输出格式】
仅包含一个正整数,表示{$1, 2,…, n$}有多少个满足上述约束条件的子集。
第一眼看上去是个组合计数问题。。。然而组合做不了,所以我们考虑DP。
考虑将题目所给的限制条件转化成一个矩阵
以从$1$开始为例:
这是矩阵 ->$\begin{bmatrix} 1 & 3 & 9 & 27 & …\ 2 & 6 & 18 & 54 & … \ 4 & 12 & 36 & 108 & … \ 8 & 24 & 72 & 216 & … \ … & … & … & … & … \end{bmatrix}
\quad$
于是乎 原问题就变成了求在这个矩阵里选一些两两不相邻的数的方案数
由于这些数是指数级增长的,所以在$100000$范围内,粗略估计矩阵的长宽最多也不会超过$20$,而$3$倍增长的列的数目更是不会超过$11$。
所以可以想到用状压DP 怎么DP就不说了 注意可以把很多没必要枚举的状态跳过,第一次写的时候被卡TLE了。。。
从$1$开始的矩阵不一定包含所有数,对于一个数,如果前面的矩阵都没有包含它,如$5, 7, 11$,需要在从这个数开始的矩阵再DP一次,答案就是每次DP出来的部分答案的积。
时间复杂度$O($一秒内$)$
【代码】
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #include <iostream> #include <cstdio> #include <cmath> #include <cstring> using namespace std; typedef long long ll;
const ll mod = 1000000001; ll n, dp[21][100005], ans = 1; ll len, len2[1005]; bool vis[100005];
inline void add(ll &x, ll y) { x += y; if (x >= mod) x -= mod; }
ll solve(ll x) { ll nowans = 0; for (int i = 1; ; i++) { ll cur = (x << (i-1)); if (cur > n) { len = i - 1; break; } vis[cur] = 1; for (int j = 1; ; j++) { cur *= 3; if (cur > n) { len2[i] = j; break; } vis[cur] = 1; } } for (int i = 0; i <= len; i++) for (int j = 0; j < (1 << len2[i]); j++) dp[i][j] = 0; dp[0][0] = 1; for (int i = 0; i < len; i++) { for (int j = 0; j < (1 << len2[i]); j++) { if (dp[i][j]) { if (j & (j << 1)) continue; for (int k = 0; k < (1 << len2[i+1]); k++) { if (k & (k << 1)) continue; if ((j & k) == 0) { dp[i+1][k] = (dp[i+1][k] + dp[i][j]) % mod; } } } } } for (int j = 0; j < (1 << len2[len]); j++) { nowans = (nowans + dp[len][j]) % mod; } return nowans; }
int main() { scanf("%lld", &n); for (int i = 1; i <= n; i++) { if (!vis[i]) { vis[i] = 1; ans = ans * solve(i) % mod; } } printf("%lld\n", ans); return 0; }
|
~~DP题目太难了 我太蒻了~~