相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4197
解题报告
考虑把小于$\sqrt{n}$的因数状压起来
然后将所有数按照大于$\sqrt{n}$的因数分组
最后分组$DP$即可
总时间复杂度:$O(500 \cdot 3^8)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 509; const int M = 6561; int pri[] = {2, 3, 5, 7, 11, 13, 17, 19}; int n, gpri[N], spri[N], sta1[M], sta2[M], tt[M][N][3]; LL MOD, *f, *g, *h, arr1[M], arr2[M], arr3[M], ori[M]; vector<int> sta[N]; inline void relax(LL &a, LL b) { a = (a + b) % MOD; } inline int num(int x, int t) { for (; t; x /= 3, t--); return x % 3; } inline int SET(int w, int t, int v) { static int buf[] = {1, 3, 9, 27, 81, 243, 729, 2187}; int ret = 0; for (int i = 0; i < 8; i++, w /= 3, t >>= 1) { if (t & 1) { ret += buf[i] * v; } else { ret += buf[i] * (w % 3); } } return ret; } int main() { freopen("dinner.in", "r", stdin); freopen("dinner.out", "w", stdout); cin>>n>>MOD; for (int i = 0; i < M; i++) { for (int j = 0; j < 8; j++) { int t = num(i, j); if (t == 1) { sta1[i] |= 1 << j; } else if (t == 2) { sta2[i] |= 1 << j; } } } for (int i = 0; i < M; i++) { for (int j = 0; j < (1 << 8); j++) { for (int k = 1; k <= 2; k++) { tt[i][j][k] = SET(i, j, k); } } } for (int i = 2; i <= n; i++) { gpri[i] = i; for (int j = 0; j < 8; j++) { if (gpri[i] % pri[j] == 0) { spri[i] |= (1 << j); while (gpri[i] % pri[j] == 0) { gpri[i] /= pri[j]; } } } } f = arr1, g = arr2, h = arr3; g[0] = f[0] = 1; for (int i = 2; i <= n; i++) { if (gpri[i] == 1) { for (int j = M - 1; ~j; j--) { if (g[j]) { int sta = 0; for (int k = 0; k < 8; k++) { if (spri[i] >> k & 1) { sta |= num(j, k); } } if (sta == 0) { relax(f[tt[j][spri[i]][1]], g[j]); relax(f[tt[j][spri[i]][2]], g[j]); } else if (sta < 3) { relax(f[tt[j][spri[i]][sta]], g[j]); } } } memcpy(g, f, sizeof(arr1)); swap(f, g); } else { sta[gpri[i]].push_back(spri[i]); } } for (int i = 2; i <= n; i++) { if (!sta[i].empty()) { memcpy(h, g, sizeof(arr1)); memcpy(ori, g, sizeof(arr1)); for (int j = 0; j < (int)sta[i].size(); j++) { int vv = sta[i][j]; for (int k = M - 1; ~k; k--) { if (g[k]) { int s1 = vv & sta1[k]; if (!s1) { relax(f[tt[k][vv][2]], g[k]); } } } memcpy(g, f, sizeof(arr1)); swap(f, g); } memcpy(f, h, sizeof(arr1)); for (int j = 0; j < (int)sta[i].size(); j++) { int vv = sta[i][j]; for (int k = M - 1; ~k; k--) { if (h[k]) { int s2 = vv & sta2[k]; if (!s2) { relax(f[tt[k][vv][1]], h[k]); } } } memcpy(h, f, sizeof(arr1)); swap(f, h); } for (int k = 0; k < M; k++) { f[k] = g[k] = (f[k] + g[k] - ori[k]) % MOD + MOD; } } } LL ans = 0; for (int i = 0; i < M; i++) { relax(ans, f[i]); } printf("%lld\n", ans); return 0; }