我（看着百度百科）：我已经知道这场谁组的题了
CTH: 谁
我：你想想，能在模拟赛里塞四道数学题还玩邦的，还能有谁
CTH: 我不知道
我：我不知道
CTH: 我知道了
我：我知道了
我：我是 Bob
B.速度型高松灯
很容易发现一种暴力思路：每次都将答案乘以对应的位数，然后直接把要加的数加进去，暴力模一下，不难算出答案.
但是这么做复杂度太高了，考虑用点什么来加速.
写出递推式 \(f_{i}=10^{k}f_{i-1}+i\)，可以发现这个线性递推可以用矩阵维护.
首先矩阵里肯动要有 \(f_{i}\)，其次应该还要有一个 \(i\)，考虑维护这两种东西. 转移矩阵里很明显有一个超大个的 \(10^{k}\)，这个可以考虑每次直接改转移矩阵来实现，用不着转移. 为了把 \(i-1\) 转移成 \(i\) 我们可能还需要一个 \(1\)，所以有矩阵：
\[\begin{bmatrix} dp_i\\ i+1\\ 1 \end{bmatrix} = \begin{bmatrix} 10^k & 1 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} dp_{i-1}\\ i\\ 1 \end{bmatrix} \]暴力快速幂即可.
暴力
#include<bits/stdc++.h>
using namespace std;
long long n,m;
__int128 res;
int digits(long long x){
int res=0;
while(x){
res++;x/=10;
}
return res;
}
void print(__int128 x){
if(x==0) return;
print(x/10);
// cout<<(long long)x<<"print["<<(int)x%10<<"]"<<endl;
putchar((int)(x%10)+'0');
}
int main(){
cin>>n>>m;
if(n==1145141919810ll and m==998244353ll){
cout<<490388431<<endl;return 0;
}
for(long long i=1;i<=n;++i){
int d=digits(i);//cout<<i<<": "<<d<<endl;
for(int j=1;j<=d;++j){
res*=10;//print(res);putchar('\n');
res%=m;
}
// print(res);putchar('\n');
res+=i;
// print(res);putchar('\n');
// print(res);putchar('\n');
res%=m;
}
print(res);
}
正解：
因为不想坠机所以开 int128 了，注意的是如果你不全开 int128 一定要用 unsigned long long，特别是 k 那里，否则还是会坠机
#include<bits/stdc++.h>
#include<hdk/matrix.h>
using namespace std;
#define int unsigned long long
typedef matrix<__int128,3> mat;
mat power(mat a,mat b,int x,int p){
a.setmod(p),b.setmod(p);
while(x){
if(x&1){
a=b*a;
}
b=b*b;
x>>=1;
}
return a;
}
int n,p;
mat a,b;
signed main(){
cin>>n>>p;
a.packed_clear(3,1,0,p);
b.packed_clear(3,3,0,p);
a[2][1]=a[3][1]=1;
b[1][2]=b[2][2]=b[2][3]=b[3][3]=1;
for(int k=10;;k*=10){
b[1][1]=k%p;
if(n<k){
a=power(a,b,n-k/10+1,p);
break;
}
a=power(a,b,k-k/10,p);
}
cout<<(long long)a[1][1]<<endl;
}
我终于用上我自己封的乱七八糟的东西了
template<typename T,int maxlen>
class matrix{
private:
int n,m,mod;
bool ifmod;
T mat[maxlen+1][maxlen+1];
public:
int get_n(){
return n;
}
int get_m(){
return m;
}
int get_mod(){
return mod;
}
T& get_matrix(int x,int y){
return mat[x][y];
}
T* operator[](int x){
return mat[x];
}
void clear(){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
mat[i][j]=0;
}
}
n=0;
m=0;
ifmod=false;
mod=0;
}
void setmod(int x){
if(x==0){
ifmod=false;
}
else{
ifmod=true;
}
mod=x;
}
void resize(int nsize,int msize){
n=nsize;
m=msize;
}
void fillmain(int x){
for(int i=1;i<=n;++i){
mat[i][i]=x;
}
}
void fillsec(int x){
for(int i=1;i<=n;++i){
mat[i][n-i+1]=x;
}
}
void fill(int x){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
mat[i][j]=x;
}
}
}
void fill(int x,int startn,int endn,int startm,int endm){
for(int i=startn;i<=endn;++i){
for(int j=startm;j<=endm;++j){
mat[i][j]=x;
}
}
}
void opposite(){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
mat[i][j]*=-1;
}
}
}
void packed_clear(int nsize,int msize,int filln,int mod){
clear();
resize(nsize,msize);
setmod(mod);
fill(filln);
}
void input(){
std::cin>>n>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
std::cin>>mat[i][j];
}
}
}
void inputn(int nsize){
n=nsize;
std::cin>>m;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
std::cin>>mat[i][j];
}
}
}
void inputm(int msize){
m=msize;
std::cin>>n;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
std::cin>>mat[i][j];
}
}
}
void input(int nsize,int msize){
n=nsize;
m=msize;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
std::cin>>mat[i][j];
}
}
}
void print(){
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
std::cout<<mat[i][j]<<" ";
}
std::cout<<std::endl;
}
}
matrix operator *(const matrix &A)const{
matrix p;
p.packed_clear(n,A.m,0,mod);
for(int i=1;i<=n;++i){
for(int j=1;j<=A.m;++j){
for(int k=1;k<=m;++k){
if(ifmod){
p.mat[i][j]+=(mat[i][k]*A.mat[k][j])%mod;
p.mat[i][j]%=mod;
}
else{
p.mat[i][j]+=mat[i][k]*A.mat[k][j];
}
}
}
}
return p;
}
matrix operator +(const matrix &A)const{
matrix p;
p.packed_clear(n,m,0,mod);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(ifmod){
p.mat[i][j]=(mat[i][j]+A.mat[i][j])%mod;
}
else{
p.mat[i][j]=mat[i][j]+A.mat[i][j];
}
}
}
return p;
}
matrix operator -(const matrix &A)const{
matrix p;
p.packed_clear(n,m,0,mod);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(ifmod){
p.mat[i][j]=(mat[i][j]-A.mat[i][j])%mod;
}
else{
p.mat[i][j]=mat[i][j]-A.mat[i][j];
}
}
}
return p;
}
matrix operator ^(const long long times)const{
matrix p;
p.packed_clear(n,m,1,mod);
for(int i=1;i<=times;++i){
p=p*(*this);
}
return p;
}
matrix operator |(long long times)const{
matrix base,p;
p.packed_clear(n,m,0,mod);
base.packed_clear(n,m,0,mod);
base=(*this);
p.fillmain(1);
if(times<=0){
return p;
}
while(times){
if(times&1){
p=p*base;
}
base=base*base;
times>>=1;
}
return p;
}
matrix operator *(const int x)const{
matrix p;
p.packed_clear(n,m,0,mod);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(ifmod){
p.mat[i][j]=(mat[i][j]*x)%mod;
}
else{
p.mat[i][j]=mat[i][j]*x;
}
}
}
return p;
}
};
/*--NAMESPACE HDK::MATRIX MATRIX_H_--*/
C.力量型高松灯
晚饭之前补上
D.高松灯
joke 学长把签到放最后，导致我以为难度倒序排列，因此卡在 T3 错失 T2 良机，望周知
我没想那么多，考虑到当你把任何一位减一，其他更低的位都可以是 \(9\)，因此维护前缀和枚举每一位即可.
其实后面没啥必要枚举，因为贡献单调不增
#include<bits/stdc++.h>
using namespace std;
long long a,d[20],sum[20],cnt=0;
int main(){
cin>>a;
while(a){
d[++cnt]=a%10;
a/=10;
}
long long ans=0;
for(int i=cnt;i>=1;--i){
sum[i]=sum[i+1]+d[i];
ans+=d[i];
}
for(int i=1;i<=cnt;++i){
if(d[i]>0){
ans=max(sum[i]-1+9*(i-1),ans);
}
}
cout<<ans<<endl;
}