【洛谷T96628】统计

叁歲伎倆 2023-06-05 08:55 39阅读 0赞

# Description #

给定$n$, $m$，求十进制$n$位数每个位数之积等于k的方案数

# Solution #

**dp+高精+数学**

考虑$k=0$的情况，由于可以有若干个$0$，所以方案数为$\\sum\\limits\_\{i=1\}^\{n\}\{n\\choose m\}\\times 9^\{n-i\}$

考虑另外的情况，我们将$k$分解质因数，如果$k$还有除了$2$,$3$,$5$,$7$之外的质因数那么方案数为$0$

其余的情况我们考虑一个$dp$,定义$f\[i\]\[j\]\[k\]\[l\]\[o\]$表示考虑前$i$位，前$i$位之积$=2^j\\times 3^k\\times 5^l\\times7^o$的方案数是多少，显然第一维可以用滚动数组压掉，转移就类似于背包的转移即可。

由于本题十分恶心的没有取模，所以我们需要高精度计算

# Code #

#include <bits/stdc++.h>
    // check if it is judged online
    #define LOCAL
    namespace shl {
        const int mod = 10;
        int n, k;
        typedef unsigned long long ull;
        ull C[55][55];
        ull ans[60];
        ull sum[60]; 
        int lens = 1, lena = 1;
        using std::max;
        int f[32][32][32][32][50];
        void add() {
            lena = max(lena, lens);
            for (register int i = 1; i <= lena; ++i)
                ans[i] += sum[i];
            for (register int i = 1; i <= lena; ++i)
                ans[i + 1] += ans[i] / mod, ans[i] %= mod;
            while (ans[lena + 1]) lena++;
        }
        void mul(ull x, ull base, int mi) {
            memset(sum, 0, sizeof(sum));
            lens = 1;
            sum[1] = 1;
            for (register int i = 1; i <= mi; ++i) {
                for (register int j = 1; j <= lens; ++j) sum[j] *= base;
                for (register int j = 1; j <= lens; ++j)
                    sum[j + 1] += sum[j] / mod, sum[j] %= mod;
                while (sum[lens + 1]) lens++;            
            }
            for (register int i = 1; i <= lens; ++i) sum[i] *= x;
            for (register int i = 1; i <= lens; ++i)
                sum[i + 1] += sum[i] / mod, sum[i] %= mod;
            while (sum[lens + 1]) lens++;
        }
        void plus(int x[60], int y[60]) {
            int c[100], len = 1;
            memset(c, 0, sizeof(c));
            len = max(x[0], y[0]);
            for (register int i = 1; i <= len; ++i)
                c[i] = x[i] + y[i];
            for (register int i = 1; i <= len; ++i)
                c[i + 1] += c[i] / mod, c[i] %= mod;
            while (c[len + 1]) len++;
            x[0] = len;
            for (register int i = 1; i <= len; ++i)
                x[i] = c[i];
        }
        int main() {
            scanf("%d%d", &n, &k);
            if (k == 0) {
                for (register int i = 0; i <= n; ++i)
                    C[i][0] = C[i][i] = 1;
                for (register int i = 1; i <= n; ++i)
                    for (register int j = 1; j < i; ++j)
                        C[i][j] = C[i - 1][j] + C[i - 1][j - 1];
                for (register int i = 1; i <= n; ++i) {
                    mul(C[n][i], 9ll, n - i);
                    add();
                }
                for (register int i = lena; i >= 1; --i)
                    printf("%d", ans[i]);
                puts("");
                return 0;
            }
            int a1 = 0, a2 = 0, a3 = 0, a4 = 0;
            while (k % 2 == 0) a1++, k /= 2;
            while (k % 3 == 0) a2++, k /= 3;
            while (k % 5 == 0) a3++, k /= 5;
            while (k % 7 == 0) a4++, k /= 7;
            if (k > 1) {
                puts("0");
                return 0;
            }
            f[0][0][0][0][0] = 1;
            f[0][0][0][0][1] = 1;
            for (register int i = 1; i <= n; ++i) {
                for (register int j = a1; j >= 0; --j)
                    for (register int k = a2; k >= 0; --k)
                        for (register int l = a3; l >= 0; --l)
                            for (register int o = a4; o >= 0; --o) {
                                if (j >= 1) plus(f[j][k][l][o], f[j - 1][k][l][o]); //2
                                if (k >= 1) plus(f[j][k][l][o], f[j][k - 1][l][o]); //3
                                   if (j >= 2) plus(f[j][k][l][o], f[j - 2][k][l][o]); //4
                                    if (l >= 1) plus(f[j][k][l][o], f[j][k][l - 1][o]); //5
                                    if (j >= 1 && k >= 1) plus(f[j][k][l][o], f[j - 1][k - 1][l][o]); //6
                                if (o >= 1) plus(f[j][k][l][o], f[j][k][l][o - 1]); //7
                                if (j >= 3) plus(f[j][k][l][o], f[j - 3][k][l][o]); //8
                                if (k >= 2) plus(f[j][k][l][o], f[j][k - 2][l][o]); //9
                            }
            }
            for (register int i = max(f[a1][a2][a3][a4][0], 1); i >= 1; --i)
                printf("%d", f[a1][a2][a3][a4][i]);
            return 0;
        }
    }
    int main() {
    #ifdef LOCAL
        freopen("count.in", "r", stdin);
        freopen("count.out", "w", stdout);
    #endif
        shl::main();
        return 0;
    }

转载于:https://www.cnblogs.com/shl-blog/p/11437788.html