jcyzoj1310: 猴猴吃香蕉

原题链接
dp计数.
f[i][j]表示考虑到前i个香蕉，乘积为j的方案数.
if j % a[i] == 0, then f[i][j] = f[i - 1][j / a[i]].
第一维滚动数组优化，第二维离散化.
代码如下：

#include using namespace std;inline int read() {int x = 0, f = 0; char ch = getchar();while (!isdigit(ch)) f = ch == '-', ch = getchar();while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();return f ? -x : x;
}const int N = 10100; 
const int mod = 1e9 + 7; 
int n, k, a[N], b[N], f[N], cnt; void AddMod(int &p, int k) { p = (p + k) % mod; }void work() {n = read(); k = read(); for (int i = 1; i <= n; ++i) a[i] = read(); cnt = 0; for (int i = 1; i * i <= k; ++i) {if (!(k % i)) {b[++cnt] = i; if (i * i != k) b[++cnt] = k / i;  }}
//	sort(a + 1, a + n + 1);  sort(b + 1, b + cnt + 1); memset(f, 0, sizeof f); for (int i = 1; i <= n; ++i) {for (int j = cnt; j >= 1; --j) {if (!(b[j] % a[i])) {int la = lower_bound(b + 1, b + cnt + 1, b[j] / a[i]) - b; if (b[la] == b[j] / a[i]) {AddMod(f[j], f[la]); 
//					printf("AddMod(f[%d], f[%d])\n", b[j], b[la]); 		}}} int now = lower_bound(b + 1, b + cnt + 1, a[i]) - b; AddMod(f[now], 1); 
//		printf("AddMod(f[%d], 1)\n", b[now]); }printf("%d\n", f[cnt]);  
}int main() {int t = read(); while (t--) work(); return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！