前言
没啥前言，摆了摆了。
题面长这个样子
思路
没啥思路，摆了摆了。
这题总的来说挺难想的，思考过程比较繁琐，我也就不辞辛劳列举一下。
-
显然，条件 \(2\) 和条件 \(3\) 很好说，放一边。
-
我们设一个质数数列 \(\{p_k\}\) ，假定这些质数是由 \(S\) 分解坤坤数
质因数得到的，若要满足条件 \(4\) （即 \(\mathbb{lcm}\{p_k\} = S\) ） ，则需要满足 \(\{p_k\}\) 中的元素两两互不相等，否则无解。\(\\\) 证明显然。 \(\\\) 设 \(sum = \sum_{i = 1}^{k}{p_i}\) ，我们讨论另一种无解的情况。当 \(n < sum\) 时无解。\(\\\) 证明如下：\(\\\) 因为 \(n\) 一定由 \(\{p_k\}\) 中的全部元素组成，当然，每个元素可以有多个。若 \(n < sum\) ，则 \(n\) 一定不能由 \(\{p_k\}\) 中的全部元素组成（因为在这种情况下 \(sum = \sum_{i = 1}^{k}{p_i} > n\) ，就算每个元素只选一个，这些选的元素相加也会比 \(n\) 大），所以便不能满足条件 \(4\) 。 -
下面我们只考虑有解的情况。乍一看，这个题很像多重背包。\(\\\) 你说得对，但是这题数据范围很大，只用多重背包会炸掉。\(\\\) 所以，我们便要采取一些优化手段。\(\\\) 设 \(S = p_i \times k_i\) ， 则 \(k_i\) 的含义便是除了坤坤子 \(p_i\) 外所有坤坤子的乘积。\(\\\) 设 \(n = \sum_{i = 1}^{k}{p_i \times c_i}\) ，\(c_i\) 是坤坤子 \(p_i\) 出现的个数，对于每一项 \(p_i \times c_i\) ，我们可以写成 \(p_i \times (x_i \times k_i + y_i),(y_i < k_i)\) ，拆开括号得 \(p_i \times k_i \times x_i + p_i \times y_i\) ，即 \(S \times x_i + p_i \times y_i , (p_i \times y_i < S)\) 。把每一项加在一起便可得 \(n = S \times \sum_{i = 1}^{k}{x_i} + \sum_{i = 1}^{k}{p_i \times y_i} , (\sum_{i = 1}^{k}{p_i \times y_i} < k \times S)\) 。简化一下（就不设了，知道什么跟什么对应就行）可得 \(n = a \times S + b,(b < k \times S)\) 。\(\\\) 有了这个式子（别管为什么能这么得到这个式子），我们便用加号前面的跑组合数，加号后面的跑
多重背包就行。 -
组合数怎么跑？对于 \(a \times S\) ，因为 \(\{p_k\}\) 中每一个元素都是 \(S\) 的约数，所以每个 \(S\) 都可以用任何一个 \(p_i\) 表示。因为有 \(k\) 个坤坤数，所以 \(S\) 最多能表示成 \(k\) 种形式（有的可以不用表示），一共有 \(a\) 个这样的数，所以转化一下就是插板法求组合数，（根据条件 \(3\) 可知是有序的）把 \(a\) 个数分成 \(k - 1\) 个可空的部分，答案显然是 \(\mathrm{C}_{a + k - 1}^{k - 1}\)。
-
背包怎么跑？我们不知道 \(a \times S\) 和 \(b\) 中是否都存在 \(p_i\) ，所以我们用 \(2\) 的 \(sum\) ，让 \(b = b - sum\) ，保证每一个 \(p_i\) 都存在，然后我们就可以跑完全背包了。这题让求方案数，
稍微改一下就行了。我们先枚举每一个坤坤子 \(p_i\) ，先都加上，然后再把多的减去即可（这里我犯懒了Orz）。
完结撒代码
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MOD(1e9 + 7), maxn(2000005);
inline LL read() {
LL f(1), x(0);
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c & 15);
return f * x;
}
LL s, q, n, cnt, sum, M, ans;
LL inv[maxn], prime[maxn], v[10], dp[7 * maxn];
void DP() {
dp[0] = 1;
for (int i = 1; i <= cnt; ++i) {
for (int j = 0; j + v[i] <= M; ++j) {
if (dp[j]) dp[j + v[i]] = (dp[j] + dp[j + v[i]] + MOD) % MOD;
}
for (int j = M - s; j >= 0; --j) {
dp[j + s] = (dp[j + s] - dp[j] + MOD) % MOD;
}
}
}
bool divide(LL n) {
LL x = n;
for (int i = 2; i <= sqrt(x); ++i) {
if (!(x % i)) {
v[++cnt] = i;
sum += i;
}
while (!(x % i)) {
++prime[i];
if (prime[i] == 2) return false;
x /= i;
}
}
if (x > 1) {
++prime[x];
v[++cnt] = x;
sum += x;
}
return true;
}
LL QuickPow(LL a, LL b, LL p) {
LL res(1);
for (; b; b >>= 1) {
if (b & 1) res = res * a % p;
a = a * a % p;
}
return res % p;
}
int main() {
s = read(), q = read();
if (!divide(s)) {
while (q--) {
n = read();
printf("0\n");
}
return 0;
}
M = cnt * s;
DP();
inv[1] = 1;
for (int i = 2; i <= 8; ++i) {
inv[i] = inv[i - 1] % MOD * QuickPow(i, MOD - 2, MOD) % MOD;
}
while (q--) {
n = read();
if (n < sum) {
printf("0\n");
continue;
}
n -= sum;
for (int i = 0; i < cnt && i <= n / s; ++i) {
LL a = n / s - i;
LL b = n % s + i * s;
int res1(1), res2(0);
res1 = inv[cnt - 1] % MOD;
for (int j = 1; j < cnt; ++j) {
res1 = res1 * ((a + j) % MOD) % MOD;
}
res1 %= MOD;
res2 = res1 % MOD * dp[b] % MOD;
ans = (ans + res2) % MOD;
}
ans = (ans % MOD + MOD) % MOD;
printf("%lld\n", ans);
ans = 0;
}
}