专栏文章

题解：AT_abc129_f [ABC129F] Takahashi's Basics in Education and Learning

IImerance1018
AT_abc129_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8mvrv
此快照首次捕获于
2025/12/01 22:21
3 个月前
此快照最后确认于
2025/12/01 22:21
3 个月前
查看原文
默认数列下标从 11 开始。
用 int128 AC 后才发现保证等差数列中的数小于 101810^{18}。

Description

给定一个长度为 LL，首项为 AA，公差为 BB 的等差数列 {sL}\{s_L\}，将数列中的所有数从左到右依次拼接得到一个新数，求该新数对给定 MM 的余数。1≤L,A,B<10181 \le L,A,B < 10^{18}。

Solution

考虑矩阵快速幂，由于转移矩阵由当前项的位数决定，需要进行分段。
将十进制下位数相同的数字放在一起考虑，易得位数为 xx 的项在数列中的下标为 [⌈10x−1−AB⌉+1,⌊10x−1−AB⌋+1][\lceil \frac{10^{x-1}-A}{B}\rceil+1,\lfloor \frac{10^{x}-1-A}{B} \rfloor+1]。
将数列分成 log⁡V\log V 段后矩阵快速幂即可。由于 LL 和 VV 同阶，复杂度 O(log⁡2V)O(\log^2 V)。

Code

CPP
#include<bits/stdc++.h>
#define int long long
#define ll __int128
using namespace std;
int l;
ll a,b;
int mod;
struct matrix
{
    int val[4][4];
    matrix(){memset(val,0,sizeof(val));}
    matrix operator *(const matrix &x)const
    {
        matrix res;
        for(int i=1;i<=3;i++)
            for(int k=1;k<=3;k++)
                for(int j=1;j<=3;j++)
                    res.val[i][j]=(res.val[i][j]+val[i][k]*x.val[k][j]%mod)%mod;
        return res;
    }
}G,base;

int getlen(ll x)
{
    int tot=0;
    while(x!=0)
    {
        tot++;
        x/=10;
    }
    return tot;
}
ll read()
{
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    ll x=0;
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x;
}
void print(ll x)
{
   if(x>9)print(x/10);
    cout<<(int)(x%10);
}
signed main()
{
    cin>>l;
    a=read();
    b=read();
    cin>>mod;
    ll tmp=1;
    for(int i=1;i<getlen(a);i++)tmp*=10;
    base.val[1][1]=base.val[1][2]=a%mod,base.val[1][3]=b%mod;
    for(int i=getlen(a);i<=getlen(a+(l-1)*b);i++)
    {
        int L=(max(tmp,a+b)-a+b-1)/b+1,R=(min(tmp*10-1,a+(l-1)*b)-a)/b+1;
        G.val[1][1]=tmp*10%mod,G.val[2][1]=G.val[2][2]=G.val[3][1]=G.val[3][2]=G.val[3][3]=1;
        int x=R-L+1;
        while(x)
        {
            if(x&1)base=base*G;
            G=G*G;
            x>>=1;
        }
        tmp*=10;
    }
    cout<<base.val[1][1]<<"\n";
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...