P9836 [lg noip A] 种树

樱雪喵 · 2023-11-11 19:42:46 · 题解

首先看到因数个数，想到在质因数分解后的序列上考虑问题。进一步观察，每个不同质因子的贡献是独立的。

也就是说，我们单独考虑某一个质因子对答案的贡献，是这样的问题：

给长度为 n 的序列 a 和一个数 w，每次操作你可以选择一个 i，令 a_i\gets a_i+1，可以重复选择同一个位置。至多操作 w 次，最大化 \prod\limits_{i=1}^n a_i。

这是一个经典问题，容易证明每次贪心操作最小值是最优的。数据范围放了 O(n^2) 通过，所以怎么实现都行。

#define int long long
const int N=1e4+5,mod=998244353;
int n,w;
int a[N],cnt[N],ans=1;
priority_queue<int,vector<int>,greater<int> >q;
il void solve(int x,int sum)
{
    for(int i=1;i<=n;i++)
    {
        cnt[i]=1;
        while(a[i]%x==0) cnt[i]++,a[i]/=x;
        q.push(cnt[i]);
    }
    while(sum) 
    {
        int x=q.top(); q.pop();
        q.push(x+1),sum--;
    }
    for(int i=1;i<=n;i++) ans=ans*q.top()%mod,q.pop();
}
signed main()
{
    n=read(),w=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=2;i*i<=w;i++) 
        if(w%i==0)
        {
            int now=0;
            while(w%i==0) now++,w/=i;
            solve(i,now);
        }
    if(w>1) solve(w,1);
    for(int i=1;i<=n;i++)
    {
        for(int j=2;j*j<=a[i];j++)
        {
            int now=1;
            while(a[i]%j==0) a[i]/=j,now++;
            ans=ans*now%mod;
        }
        if(a[i]>1) ans=ans*2%mod;
    }
    printf("%lld\n",ans);
    return 0;
}