[ARC182C] Sum of Number of Divisors of Product 题解

题目链接

点击打开链接

题目解法

我怎么不会分治/fn

首先把 \(x\) 分解成 \(\prod p_i^{x_i}(0\le i\le 5)\) 的形式，正因数个数为 \(\prod (x_i+1)\)
有一个很牛的想法是：合并两个 \(x_i\) 序列（假设一个叫 \(x_0,...,x_5\)，另一个叫 \(y_0,...,y_5\)）
先不考虑后面的 \(+1\)（可以最后在合并上去），想一想 \((x_0+y_0)(x_1+y_1)...(x_5+y_5)\) 的意义是什么？
我们把括号拆开，意义是选择一个 \(0,...,5\) 的子集，集合内的用 \(x\) 乘，集合外的用 \(y\) 乘，即维护出子集的乘积和，就能轻松合并两个序列

这样就简单了，我们倍增求答案即可
因为要求的是历史和，所以当前值和历史和都维护即可
时间复杂度 \(O(60\times 3^6)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int P=998244353,M=1<<6;
LL n;
int m,pr[6]={2,3,5,7,11,13};
typedef vector<int> vi;
vi f[60],g[60];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
vi merge(vi v1,vi v2){
    vi rec(M,0);
    F(S,0,M-1)
        for(int T=S;;T=(T-1)&S){
            inc(rec[S],1ll*v1[T]*v2[S^T]%P);
            if(!T) break;
        }
    return rec;
}
int main(){
    read(n),read(m);
    f[0].resize(M);
    F(i,1,m)
        F(S,0,M-1){
            int x=i,val=1;
            F(j,0,5) if(S>>j&1){
                int c=0;
                while(x%pr[j]==0) c++,x/=pr[j];
                val*=c;
            }
            inc(f[0][S],val);
        }
    g[0]=f[0];
    F(i,1,59){
        g[i]=merge(g[i-1],g[i-1]);
        f[i]=merge(f[i-1],g[i-1]);
        F(j,0,M-1) inc(f[i][j],f[i-1][j]);
    }
    vi ans(M,0),cur(M,0);
    bool fir=1;
    F(i,0,59) if(n>>i&1){
        if(fir) ans=f[i],cur=g[i],fir=0;
        else{
            vi t=merge(cur,f[i]);
            F(j,0,M-1) inc(ans[j],t[j]);
            cur=merge(cur,g[i]);
        }
    }
    ans=merge(ans,vi(M,1));
    printf("%d\n",ans[M-1]);
    return 0;
}