首页 > 其他 > 详细

[CF893E] Counting Arrays - 组合计数

时间:2021-03-05 12:12:39      阅读:17      评论:0      收藏:0      [点我收藏+]

[CF893E] Counting Arrays - 组合计数

Description

给出x和y,求一个长度为y的序列,其乘积为x,允许有负数,求这种序列的个数,对1e9+7取模。

Solution

其实就是分配质因子,而且每个质因子还是独立的

先考虑绝对值

单独考虑每个质因子的分配,假设有 q 个,我们要分配给 n 个位置,每个位置非负整数

这样的方案数用隔板法算,先变成 n+q 个,然后在 n+q-1 个间隔中选 n-1 个放隔板,即 C(n+q-1,n-1)

不同的质因子之间,方案数通过乘法原理乘在一起

至于符号,额外乘个枚举子集的方案数即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 1e9 + 7;

namespace math_mod
{
    int c__[5005][5005], fac__[3000005];

    int qpow(int p, int q)
    {
        return (q & 1 ? p : 1) * (q ? qpow(p * p % mod, q / 2) : 1) % mod;
    }

    int inv(int p)
    {
        return qpow(p, mod - 2);
    }

    int fac(int p)
    {
        if (p <= 3000000)
            return fac__[p];
        if (p == 0)
            return 1;
        return p * fac(p - 1) % mod;
    }

    int __fac(int p)
    {
        return fac(p);
    }

    int ncr(int n, int r)
    {
        if (r < 0 || r > n)
            return 0;
        return fac(n) * inv(fac(r)) % mod * inv(fac(n - r)) % mod;
    }

    void math_presolve()
    {
        fac__[0] = 1;
        for (int i = 1; i <= 3000000; i++)
        {
            fac__[i] = fac__[i - 1] * i % mod;
        }
        for (int i = 0; i <= 5000; i++)
        {
            c__[i][0] = c__[i][i] = 1;
            for (int j = 1; j < i; j++)
                c__[i][j] = c__[i - 1][j] + c__[i - 1][j - 1], c__[i][j] %= mod;
        }
    }

    int __c(int n, int r)
    {
        if (r < 0 || r > n)
            return 0;
        if (n > 5000)
            return ncr(n, r);
        return c__[n][r];
    }
}

using namespace math_mod;

void solve()
{
    int m, n;
    cin >> m >> n;

    int ans = 1;
    int tmp = m;
    for (int i = 2; i * i <= m; i++)
    {
        int q = 0;
        while (tmp % i == 0)
        {
            tmp /= i;
            q++;
        }
        if (q)
        {
            ans *= __c(n + q - 1, q);
            ans %= mod;
        }
    }
    if (tmp > 1)
    {
        int q = 1;
        ans *= __c(n + q - 1, q);
        ans %= mod;
    }
    cout << ans * qpow(2, n - 1) % mod << endl;
}

signed main()
{
    ios::sync_with_stdio(false);

    math_presolve();

    int t;
    cin >> t;

    while (t--)
    {
        solve();
    }
}

[CF893E] Counting Arrays - 组合计数

原文:https://www.cnblogs.com/mollnn/p/14485235.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!