自测题目solution（num）

__H_J_M__ · 2025-10-21 20:13:03 · 个人记录

solution

总体思路

矩阵加速DP

首先我们可以将题目分为两个部分从 1~r 和从 1\~(l-1);
因此题目就变成了求从 1\~n 间隔为c时的答案。

我们可以先列出基础的DP转移方程。

设f_i为从 1~n 间隔为 c 时的答案。

f_i=(f_{i-c}*10^{\lg i}+i )~mod~m

由于 c<=5，

设 k = 10^{\lg i},因此可以轻松构造矩阵。

\begin{bmatrix} f_{i-1} & f_{i-2} & f_{i-3} & f_{i-4} & f_{i-5} & i & 1 \end{bmatrix}

\begin{bmatrix} 0/k & 1 & 0 & 0 & 0 & 0 & 0\\ 0/k & 0 & 1 & 0 & 0 & 0 & 0\\ 0/k & 0 & 0 & 1 & 0 & 0 & 0\\ 0/k & 0 & 0 & 0 & 1 & 0 & 0\\ 0/k & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1\\ \end{bmatrix}

(这里标注着 0/k 的五个位置根据 c 放置 k )

（这道题目完全可以用3*3的矩阵做）

这时候我们就知道了两个部分分别的答案，我们考虑将其合并。如下：

6 2 1 100000000000000000//就是不用取模。

//第一部分 1~5
ans1=12345
//第二部分 1~8
ans2=12345678

我们需要将 ans1 乘上若干个零，并用 ans2 减去它。
所以我们需要知道中间缺失的 0 的数量，其实就是从 l 到 r 的数位数量。

当时脑子中全是矩阵，于是又写了一个。

f_i=f_{i-c}+\lg i

设 k = \lg i,因此可以轻松构造矩阵。

\begin{bmatrix} f_{i-1} & f_{i-2} & f_{i-3} & f_{i-4} & f_{i-5} &1 \end{bmatrix}

\begin{bmatrix} 0/1 & 1 & 0 & 0 & 0 & 0\\ 0/1 & 0 & 1 & 0 & 0 & 0\\ 0/1 & 0 & 0 & 1 & 0 & 0\\ 0/1 & 0 & 0 & 0 & 1 & 0\\ 0/1 & 0 & 0 & 0 & 0 & 0\\ k & 0 & 0 & 0 & 0 & 1 &\\ \end{bmatrix}

这一部分也可以直接算出来，完全不用这么麻烦

特殊情况

当c=0,需要特判。

这里十分简单,就不多说了。

/*仅供参考，完全不用这么长*/
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int l,r,Mod,c;
struct matrix{
    int a[10][10];
    matrix(){
        memset(a,0,sizeof a);
    }
    void print(){
        for(int i=1;i<=7;i++){
            for(int j=1;j<=7;j++) cout<<a[i][j]<<' ';
            cout<<'\n';
        }
    }
    friend matrix operator *(matrix a,matrix b){
        matrix c;
        for(int i=1;i<=7;i++)
            for(int j=1;j<=7;j++)
                for(int x=1;x<=7;x++)
                    c.a[i][j]=(c.a[i][j]+a.a[i][x]*b.a[x][j]%Mod)%Mod;
        return c;
    }
    friend matrix pow(matrix z,matrix x,int y){
        matrix ans=z;
        while(y){
            if(y&1) ans=ans*x;
            x=x*x;
            y>>=1;
        }
        return ans;
    }
}A,B;
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
int ask(int x){
    int ans=0;
    while(x){
        ans++;
        x/=10;
    }
    return ans;
}
int ipow(int x,int y){
    int ans=1;
    while(y){
        if(y&1) ans=ans*x%Mod;
        x=x*x%Mod,y>>=1;
    }
    return ans;
}
//这里是解决答案
void init(){
    memset(A.a,0,sizeof A.a);
    memset(B.a,0,sizeof B.a);
    A.a[1][6]=A.a[1][7]=1;
    B.a[1][2]=B.a[2][3]=B.a[3][4]=B.a[4][5]=1;
    B.a[6][6]=B.a[7][6]=B.a[7][7]=1;
    B.a[6][1]=1;
}
int solve(int n,int c){
    if(n<=c) return n;
    init();
    for(int k=10;;k=k*10){
        B.a[c][1]=k%Mod;
        if(k>n){
            A=pow(A,B,n-k/10+1);
            break;
        }
        A=pow(A,B,k-k/10);
    }
    return A.a[1][1];
}
//求出len
void init2(){
    memset(A.a,0,sizeof A.a);
    memset(B.a,0,sizeof B.a);
    A.a[1][6]=1;
    B.a[1][2]=B.a[2][3]=B.a[3][4]=B.a[4][5]=B.a[6][6]=1;
}
int solve2(int n,int c){//总一到n公差为c的位数和.
    if(n<=c) return 1;
    init2();
    for(int k=10,i=1;;k=k*10,i++){
        B.a[c][1]=1;
        B.a[6][1]=i;
        if(k>n){
            A=pow(A,B,n-k/10+1);
            break;
        }
        A=pow(A,B,k-k/10);
    }
    return A.a[1][1];
}
//解决c=0
int solve3(int x,int n){//x重复n次
    memset(A.a,0,sizeof A.a);
    memset(B.a,0,sizeof B.a);
    A.a[1][2]=1;
    B.a[1][1]=ipow(10,ask(x));
    B.a[2][1]=x;
    B.a[2][2]=1;
    A=pow(A,B,n);
    return A.a[1][1];
}
/*!@#$%^&*!@#$%^&*~~优美的分界线~~*&^%$#@!*&^%$#@!*/
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>l>>r>>c>>Mod;
    if(c==0){
        cout<<solve3(l,r+1);
        return 0;
    }
    r=l+r*c;
    if(l<=c){
        cout<<solve(r,c);
        return 0;
    }
    l-=c;
    int M=Mod;
    Mod=100000000000000ull;
    int len=solve2(r,c)-solve2(l,c);
    Mod=M;
    cout<<(solve(r,c)-solve(l,c)*ipow(10ull,len)%Mod+Mod)%Mod;
    return 0;
}
/*dp[i]=dp[i-c]*k+(i-c)+c mod m*/
/*f[i]=f[i-c]+k*/
/*f[i]=f[i-1]*k+l*/

部分分

暴力 40 分