「ARC020C」 A mod B Problem

题意

最开始有一个空的数 \(s\)，给定 \(n\) 组整数 \(a,l\)，表示把 \(a\) 复制 \(l\) 次再粘贴到 \(s\) 后，求最终 \(s\) 对 \(b\) 取模的值。

分析

考虑用 \(s_{i}\) 表示第 \(i\) 次操作后的值，我们只需要模拟每一次操作就行了，但是这个 \(l\) 的范围卡的很死。

但我们发现 \(n\) 不是很大且刚好学完矩乘，所以考虑矩阵优化递推，然后发现这题和 ABC129F 很像了。

用矩阵 \([s_i,1]\) 表示一次操作后的数据（由于要加 \(a_{i-1}\)，所以有一位常数项），我们要做的是从 \([s_{i-1},1]\) 转移过来，设 \(lg\) 为 \(\lfloor\log_{10} a_{i-1}\rfloor+1\)，可以构造出转移矩阵 \(tot\)：

初始矩阵 \(ans\) 为 \([0,1]\)，每次更新答案为 \(ans\times tot^l\)。注意取模，一定要给 \(10^{lg}\) 和 \(a_{i-1}\) 取模！

最终时间复杂度为 \(O(n\log l)\)，有 \(2^3\) 的常数。

Code

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
#define dbg(x) cout<<#x<<": "<<x<<"\n"
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
const ll maxn=1e4+5,maxt=2;
ll n,mod;
struct node{ll a,l;}p[maxn];
struct matrix{
    ll mat[maxt][maxt];
    inline matrix operator*(const matrix&u)const{
        matrix res;
        memset(res.mat,0,sizeof(res.mat));
        for(ll i=0;i<maxt;++i){
            for(ll j=0;j<maxt;++j){
                for(ll k=0;k<maxt;++k){
                    res.mat[i][j]=(res.mat[i][j]+mat[i][k]*u.mat[k][j]%mod+mod)%mod;
                }
            }
        }
        return res;
    }
}ans;
inline matrix qpow(matrix a,ll b){
    matrix res;
    memset(res.mat,0,sizeof(res.mat));
    for(ll i=0;i<maxt;++i)res.mat[i][i]=1;
    while(b){
        if(b&1)res=res*a;
        a=a*a,b>>=1;
    }
    return res;
}
signed main(){
    n=read();
    for(ll i=1;i<=n;++i)p[i].a=read(),p[i].l=read();
    mod=read();
    memset(ans.mat,0,sizeof(ans.mat));
    ans.mat[0][1]=1;
    for(ll i=1;i<=n;++i){
        ll lg=1,A=p[i].a;
        while(A)A/=10,lg*=10;
        matrix tot;
        memset(tot.mat,0,sizeof(tot.mat));
        tot.mat[0][0]=lg%mod,tot.mat[0][1]=0;
        tot.mat[1][0]=p[i].a%mod,tot.mat[1][1]=1;
        ans=ans*qpow(tot,p[i].l);
    }
    printf("%lld\n",ans.mat[0][0]);
    return 0;
}