[ARC182C] Sum of Number of Divisors of Product

· · 题解

题目传送门

首先将数质因数分解，两个数相乘就是指数相加，答案就是指数加一再相乘，可以用矩阵维护。

显然我们要维护 \sum \prod\limits_{i=1} ^6(c_i+1)（只有 6 个质数）。每次加入一个数会变成 \sum \prod \limits_{i=1}^6(c_i+1+c_i')。多项式展开后，其实我们要维护的就是一个子集卷积的过程。设 f_s=\prod \limits_{i\in s}c_i，将矩阵 g 初始化为 1，显然转移就是 g'_s=\sum\limits_{t\sub s} g_t \times f_{s/t}。拿矩阵维护一下这个东西就好了。

#include<bits/stdc++.h>
#define LL long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;

const int N=(1<<6)+10,M=(1<<6),MOD=998244353;
const int p[7]={0,2,3,5,7,11,13};

LL n;
int m;
int c[20][10],f[N];

void addm(int &x,int y){(x+=y<0? MOD+y:y)%=MOD;}

struct Matrix
{
    int v[N][N];

    Matrix(){memset(v,0,sizeof(v));}

    friend Matrix operator * (const Matrix &A,const Matrix &B)
    {
        Matrix C;
        for(int i=0; i<=M; i++)
            for(int j=0; j<=M; j++)
                for(int k=0; k<=M; k++)
                    addm(C.v[i][j],1LL*A.v[i][k]*B.v[k][j]%MOD);
        return C;
    }
}A,Ans;

void divide(int x)
{
    int tmp=x;
    for(int i=1; i<=6; i++)
        while(tmp%p[i]==0)
            c[x][i]++, tmp/=p[i];
    for(int s=0; s<M; s++)
    {
        int cur=1;
        for(int i=1; i<=6; i++)
            if(s&(1<<(i-1))) cur*=c[x][i];
        f[s]+=cur;
    }
}

int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);

    scanf("%lld%d",&n,&m);

    for(int i=1; i<=m; i++)
        divide(i);

    for(int i=0; i<M; i++)
        Ans.v[0][i]=1;
    for(int s=0; s<M; s++)
    {
        A.v[0][s]=f[s];
        if(s==M-1) A.v[0][M]=f[s];
        for(int t=s; t; t=(t-1)&s)
        {
            A.v[t][s]=f[s^t];
            if(s==M-1) A.v[t][M]=f[s^t];
        }
    }
    A.v[M][M]=1;

    while(n)
    {
        if(n&1) Ans=Ans*A;
        A=A*A; n>>=1;
    }   

    printf("%d\n",Ans.v[0][M]);

    return 0;
}