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的矩阵做）

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

CPP

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,需要特判。

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

CPP

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131/*仅供参考，完全不用这么长*/
#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 分

自测题目solution（num）

文章操作

solution

总体思路

特殊情况

部分分

相关推荐

评论

自测题目solution（num）