题解：CF2236F2 Elections in Saransk (hard version)

· · 题解

好题。

考虑质因数分解最小公倍数和乘积，对于每个质因子，最小公倍数对于该质因子的指数为选中的数的最大值，乘积为和。因此枚举 x 的每个质因子，处理如下的问题：

问题转化为已知 \{b_i\}，试计数 c_i\leq b_i，求 f_{ma,sum}，选的数最大值为 ma，和为 sum。且 sum-ma=p，其中 p 是 x 对应质因子的指数。特判 ma=sum 的情况以避免枚举所有数，对于这种数方案数为：令 s 的乘积被分解后对应的指数为 d，则方案为 d+1。

不妨钦定最大值小于等于 ma，令 b_i=\min(b_i,ma)，由此我们将问题直接转化为 c_i\leq b_i 求和，有转移公式：

f_{i,j}\leftarrow \sum_{c=0}^{b_i} f_{i-1,j-c}

考虑前缀和优化。在此处，可能最大值并不严格等于 ma，可能等于 ma-1 等，我们将 ma 时的答案与 ma-1 做差即可完成。使用乘法原理将所有质因子对应的答案相乘，我们在 O(n\log^3 V) 的时间复杂度内解决了问题。

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int dc = 1,n,x,a[100005],b[100005],pr[500005],c[35],dp[65],lst[65],sum[65];
const int md = 1e9 + 7;
namespace DoubleQLzn
{
    void init()
    {
        return ;    
    }
    void prime()
    {
        for (int i = 2;i <= 500000;i++)
        {
            for (int j = i + i;j <= 500000;j = j + i) pr[j] = 1;
        }
    }
    vector<pair<int,int>> factor(int x)
    {
        vector<pair<int,int>> ans;
        if (!pr[x])
        {
            ans.push_back({x,1});
            return ans;
        }
        for (int p = 2;x != 1;p++)
        {
            int s = 0;
            while (x % p == 0) 
            {
                s++;
                x /= p;
            }
            if (s == 0) continue;
            ans.push_back({p,s});
        }
        return ans;
    }
    void solve()
    {
        map<int,int> mp;
        cin >> n >> x;
        for (int i = 1;i <= n;i++) 
        {
            cin >> a[i];
            int s = a[i];
            for (int j = 2;j * j <= s;j++)
            {
                if (!pr[j] && s % j == 0)
                {
                    while (s % j == 0)
                    {
                        s /= j;
                        mp[j]++;
                    }
                }
            }
            if (s != 1) mp[s]++;
        }
        vector<pair<int,int>> now = factor(x);
        int ans = 1;
        for (int u = 0;u < now.size();u++)
        {
            int p = now[u].first,f = now[u].second;
            for (int j = 1;j <= 30;j++) c[j] = 0;
            for (int j = 1;j <= n;j++)
            {
                b[j] = 0;
                while (a[j] % p == 0)
                {
                    a[j] /= p;
                    b[j]++;
                }
                c[b[j]]++;
            }
            int k = 1,ma;
            for (int j = 1;;j++)
            {
                k = k * p;
                if (k > 500000)
                {
                    ma = j;
                    break;
                }
            }
            int now = 0;
            dp[0] = sum[0] = 1;
            for (int k = 1;k <= 2 * ma;k++) sum[k] = 1;
            for (int k = 0;k <= 2 * ma;k++) lst[k] = 0;
            for (int i = 0;i <= ma;i++)
            {
                dp[0] = sum[0] = 1;
                for (int k = 1;k <= 2 * ma;k++) dp[k] = 0;
                for (int k = 1;k <= 2 * ma;k++) sum[k] = 1;
                for (int j = 1;j <= n;j++)
                {
                    for (int k = 0;k <= 2 * ma;k++) 
                    {
                        int c = min(b[j],i);
                        dp[k] = (sum[k] - (k - c - 1 < 0 ? 0 : sum[k - c - 1]) + md) % md;
                    }
                    for (int k = 0;k <= 2 * ma;k++)
                    {
                        if (k == 0) sum[0] = dp[0];
                        else sum[k] = (sum[k - 1] + dp[k]) % md;
                    }
                }
                int qwq = (dp[i + f] - lst[i + f] + md) % md;
                for (int k = 0;k <= 2 * ma;k++) lst[k] = dp[k];
                now = (now + qwq) % md;
            }
            ans = (ans * now) % md;
        }
        for (auto u : mp) 
        {
            if (x % u.first != 0) ans = (ans * (1 + u.second)) % md;
        }
        cout << ans << '\n';
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    DoubleQLzn::prime();
    int T;
    if (dc == 0) T = 1;
    else cin >> T;
    while (T--)
    {
        DoubleQLzn::init();
        DoubleQLzn::solve();
    }
    return 0;
}