国产美女主播视频一区_国产精品蜜臀在线观看_亚洲成人动漫一区_亚洲视屏在线播放

(資料圖片)

前言

沒(méi)啥前言，擺了擺了。

題面長(zhǎng)這個(gè)樣子

思路

沒(méi)啥思路，擺了擺了。這題總的來(lái)說(shuō)挺難想的，思考過(guò)程比較繁瑣，我也就不辭辛勞列舉一下。

1. 顯然，條件 \(2\) 和條件 \(3\) 很好說(shuō)，放一邊。

2. 我們?cè)O(shè)一個(gè)質(zhì)數(shù)數(shù)列 \(\{p_k\}\) ，假定這些質(zhì)數(shù)是由 \(S\) 分解坤坤數(shù)質(zhì)因數(shù)得到的，若要滿(mǎn)足條件 \(4\) （即 \(\mathbb{lcm}\{p_k\} = S\) ） ，則需要滿(mǎn)足 \(\{p_k\}\) 中的元素兩兩互不相等，否則無(wú)解。\(\\\) 證明顯然。 \(\\\) 設(shè) \(sum = \sum_{i = 1}^{k}{p_i}\) ，我們討論另一種無(wú)解的情況。當(dāng) \(n < sum\) 時(shí)無(wú)解。\(\\\) 證明如下：\(\\\) 因?yàn)?\(n\) 一定由 \(\{p_k\}\) 中的全部元素組成，當(dāng)然，每個(gè)元素可以有多個(gè)。若 \(n < sum\) ，則 \(n\) 一定不能由 \(\{p_k\}\) 中的全部元素組成（因?yàn)樵谶@種情況下 \(sum = \sum_{i = 1}^{k}{p_i} > n\) ，就算每個(gè)元素只選一個(gè)，這些選的元素相加也會(huì)比 \(n\) 大），所以便不能滿(mǎn)足條件 \(4\) 。

3. 下面我們只考慮有解的情況。乍一看，這個(gè)題很像多重背包。\(\\\) 你說(shuō)得對(duì)，但是這題數(shù)據(jù)范圍很大，只用多重背包會(huì)炸掉。\(\\\) 所以，我們便要采取一些優(yōu)化手段。\(\\\) 設(shè) \(S = p_i \times k_i\) ， 則 \(k_i\) 的含義便是除了坤坤子 \(p_i\) 外所有坤坤子的乘積。\(\\\) 設(shè) \(n = \sum_{i = 1}^{k}{p_i \times c_i}\) ，\(c_i\) 是坤坤子 \(p_i\) 出現(xiàn)的個(gè)數(shù)，對(duì)于每一項(xiàng) \(p_i \times c_i\) ，我們可以寫(xiě)成 \(p_i \times (x_i \times k_i + y_i),(y_i < k_i)\) ，拆開(kāi)括號(hào)得 \(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)\) 。把每一項(xiàng)加在一起便可得 \(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)\) 。簡(jiǎn)化一下（就不設(shè)了，知道什么跟什么對(duì)應(yīng)就行）可得 \(n = a \times S + b,(b < k \times S)\) 。\(\\\) 有了這個(gè)式子（別管為什么能這么得到這個(gè)式子），我們便用加號(hào)前面的跑組合數(shù)，加號(hào)后面的跑多重背包就行。

4. 組合數(shù)怎么跑？對(duì)于 \(a \times S\) ，因?yàn)?\(\{p_k\}\) 中每一個(gè)元素都是 \(S\) 的約數(shù)，所以每個(gè) \(S\) 都可以用任何一個(gè) \(p_i\) 表示。因?yàn)橛?\(k\) 個(gè)坤坤數(shù)，所以 \(S\) 最多能表示成 \(k\) 種形式（有的可以不用表示），一共有 \(a\) 個(gè)這樣的數(shù)，所以轉(zhuǎn)化一下就是插板法求組合數(shù)，（根據(jù)條件 \(3\) 可知是有序的）把 \(a\) 個(gè)數(shù)分成 \(k - 1\) 個(gè)可空的部分，答案顯然是 \(\mathrm{C}_{a + k - 1}^{k - 1}\)。

5. 背包怎么跑？我們不知道 \(a \times S\) 和 \(b\) 中是否都存在 \(p_i\) ，所以我們用 \(2\) 的 \(sum\) ，讓 \(b = b - sum\) ，保證每一個(gè) \(p_i\) 都存在，然后我們就可以跑完全背包了。這題讓求方案數(shù)，稍微改一下就行了。我們先枚舉每一個(gè)坤坤子 \(p_i\) ，先都加上，然后再把多的減去即可（這里我犯懶了Orz）。

完結(jié)撒代碼

#include #define LL long longusing 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;    }}