\(145pts，Rank 10\)，众数分。 数学专题模拟赛%%%
总结写前面：
1. 线性递推式复杂度过大考虑矩阵快速幂优化；
2. T1 长时间切不了就先跳，先把所有题看一遍，拿分为主。
赛时记录
正常开 T1，期望数学题，大概读懂了，手模下小样例，模了一遍又一遍，“我并不认为样例是对的”，跳了（很正确的决定）。
T2，貌似也只会个 \(25pts\) 暴力，不过看起来挺可做的，先打了暴力，想着能不能找到规律，毕竟 \(n<=10^{18}\)，好吧，并不可以。
T3，又是数学，推式子题，好熟悉的式子，莫比乌斯反演，不会...，\(O(n^2 \log n)\) 可以拿 \(10pts\) 暴力，额...思考，回忆关于莫比乌斯反演以及双西格玛后面挪到前面。
不小心发现小孩哥们在打水题比赛，报名了一下，哇，好水，用了两分钟切了 T1、T2，爽。诶， IOI 赛制的，看排行榜，E 题还没人 AC，拿个首 A 我就跑，打表 AC 完发现首 A 被抢了，气！他们还挺牛，现在就剩 C 题没人 A 了，看 C 题，牛棚回声，这我熟悉啊，三分钟 A 了，发现首 A 又有人抢了！诶，不过怎么 Rank 1 了，感觉大事不妙，不会被发现吧，溜了溜了。
大概两分钟之后，huge:（叫我名）过来。
走过去，看见 Delov 学长在旁边，芭比Q，猜到是被发现了，被 D 了一顿。然后回来乖乖打比赛坐牢。
打了 T3 暴力，真不会了，开 T4 看看吧，！！不是，原来签到题放 T4 了，迅速切了，然后由于这一场就会这一题，万一再挂就祭了，于是打了个暴力跑对拍，十分钟没拍到 WA 的点，放心了。
回去看了下小孩哥模拟赛的排行榜，发现自己成绩被取消了，刷新一下，比赛页面也看不见了。。。
之后就是在 T1 模样例仍然觉得样例不对，T2 想各种可能做法，T3 使劲回忆、卡常 之间来回跳，三道题正解都无果，不过 T3 记忆化一下，发现可以优化到 \(O(n^2)\)，\(20pts\) 了，再度卡常，把四个 if 判断换成了三目运算符，（一句话里面套了五六对括号）。现在 \(145pts\) 了，剩下时间，一直坐牢了？。
我也完结撒花？
B.速度型高松灯 \(25pts\)
矩阵快速幂？，还真不会这个了，矩阵乘？，咋用啊，学过我记得，但学啥了呀。不是，矩阵乘法为啥这样乘啊......
哎，填坑 ing，看到之前提高组某一块的专题，好多都忘了，之前挖的坑现在果然还是要亲手填。
正解：
易得：\(f_i = 10 ^ k \times f_{i-1} + i\)，很线性的一个递推式，但 \(n\) 过大，所以考虑拿矩阵快速幂优化。有下列矩阵转移：
\[ \begin{bmatrix} f_i & i+1 & 1 \end{bmatrix} = \begin{bmatrix} 10^k & 0 & 0 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{bmatrix} \times \begin{bmatrix} f_{i-1} & i & 1 \end{bmatrix} \]构造矩阵转移即可。
code：
#include <bits/stdc++.h>
typedef unsigned long long ull;
#define ull __int128
using namespace std;
const int N = 5;
long long n; int m;
struct matrix{
int H, L; ull a[N][N];
void zero(){
memset(a, 0, sizeof a);
}
void one(){
zero();
for(int i=1; i<=H; i++) a[i][i] = 1;
}
void resize(int x, int y){
H = x, L = y;
}
matrix operator * (const matrix &A) const{
matrix res;
res.zero(); res.resize(H, A.L);
for(int i=1; i<=3; i++){
for(int j=1; j<=3; j++){
for(int k=1; k<=3; k++){
res.a[i][j] = (res.a[i][j] + a[i][k] * A.a[k][j] % m) % m;
}
}
}
return res;
}
}A;
matrix qpow(matrix X, ull b){
matrix res;
res.resize(X.H, X.L); res.one();
while(b)
{
if(b & 1) res = res * X;
X = X * X;
b >>= 1;
}
return res;
}
ull Mont_Mary(ull x, ull b){
ull a = x, res = 1;
while(b)
{
if(b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
int main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n>>m;
ull x = n; int cnt = 0;
while(x) x /= 10, cnt++;
A.resize(1, 3); A.a[1][2] = A.a[1][3] = 1, A.a[1][1] = 0;
matrix base; base.resize(3, 3);
ull num = 9;
for(int i=0; i<cnt; i++){
ull k = num / 9 * 10;
base.one(); base.a[2][1] = base.a[3][2] = 1, base.a[1][1] = k;
if(i == cnt - 1) break;
A = A * qpow(base, num);
num *= 10;
}
A = A * qpow(base, n - Mont_Mary(10, cnt-1) + 1);
int ans = A.a[1][1];
cout<<ans;
return 0;
}
C.力量型高松灯 \(20pts\)
听说这是学长让我们学习莫反的把戏，不赞同 但确实有效果
正解：
我并不想写这个式子过了
D.高松灯 \(100pts\)
水题放最后，差点进坑，本来打到 T3 我可能就要耗死了，还好看了眼 T4。
正解：
两种情况，一个是数自己，一个是首位数 \(-1\)，其他位全都为 \(9\)。
code：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int n;
int num[20];
signed main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin>>n;
int x = n, cnt = 0, sum = 0;
while(x)
{
num[++cnt] = x % 10;
sum += num[cnt];
x /= 10;
}
int s = (cnt - 1) * 9 + num[cnt] - 1;
cout<<max(s, sum);
return 0;
}