Rank
A. 黑暗型高松灯
原[CF1025G] Company Acquisitions
第一题直接上黑。
B. 速度型高松灯
想递推来着，但确实没考虑矩阵加速。
对矩阵的掌握感觉也没那么好了，找机会复习得。
按照下发题解里的矩阵是这样的：
\[\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} \]注意这个 \(k\) 是指 \(i\) 的位数，所以在对 \(n\) 以下不同位数要不同考虑。
还有就是，矩阵里的 \(10^k\) 这一项可以提前取模，但指数上不行，所以求这一项的时候保留原型。
点击查看丑陋的代码
#include<bits/stdc++.h>
#define fo(x,y,z) for(register int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(register int (x)=(y);(x)>=(z);(x)--)
using namespace std;
typedef unsigned long long ll;
#define lx ll
inline lx qr()
{
char ch=getchar();lx x=0,f=1;
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
#undef lx
#define qr qr()
const int Ratio=0;
const int N=2e5+5;
ll n,mod;
int tot;
struct rmm
{
ll a[5][5];
rmm(){memset(a,0,sizeof a);}
};
rmm mul(rmm a,rmm b,int x,int y,int z)
{
rmm c;
fo(i,0,x-1)
fo(j,0,y-1)
fo(k,0,z-1)
c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j]%mod+mod)%mod;
return c;
}
rmm pow(rmm a,ll t)
{
rmm b;
fo(i,0,2) b.a[i][i]=1;
while(t)
{
if(t&1) b=mul(a,b,3,3,3);
a=mul(a,a,3,3,3);
t>>=1;
}
return b;
}
namespace Wisadel
{
ll Wqp(ll x,ll y)
{
ll res=1;
while(y)
{
if(y&1) res=res*x;
x=x*x;
y>>=1;
}
return res;
}
short main()
{
// freopen(".in","r",stdin),freopen(".out","w",stdout);
n=qr,mod=qr;
ll xax=n;
while(xax) tot++,xax/=10;
rmm aa,bb;
aa.a[0][0]=0,aa.a[0][1]=1,aa.a[0][2]=1;
// bb.a[0][1]=0,bb.a[0][2]=0;
// bb.a[1][0]=1,bb.a[1][1]=1,bb.a[1][2]=0;
// bb.a[2][0]=0,bb.a[2][1]=1,bb.a[2][2]=1;
fo(i,1,tot-1)
{// 位数
ll bol=Wqp(10,i);
bb.a[0][0]=bol%mod,bb.a[0][1]=0,bb.a[0][2]=0;
bb.a[1][0]=1,bb.a[1][1]=1,bb.a[1][2]=0;
bb.a[2][0]=0,bb.a[2][1]=1,bb.a[2][2]=1;
bb=pow(bb,bol-bol/10);
aa=mul(aa,bb,1,3,3);
}
ll bol=Wqp(10,tot);
bb.a[0][0]=bol%mod,bb.a[0][1]=0,bb.a[0][2]=0;
bb.a[1][0]=1,bb.a[1][1]=1,bb.a[1][2]=0;
bb.a[2][0]=0,bb.a[2][1]=1,bb.a[2][2]=1;
bb=pow(bb,n+1-bol/10);
aa=mul(aa,bb,1,3,3);
printf("%lld\n",aa.a[0][0]);
return Ratio;
}
}
signed main(){return Wisadel::main();}
C. 力量型高松灯
感觉不是那么简单，需要用莫反，硬推式子应该也能做，等我推一推。
D. 高松灯
调换 T1 T4 顺序可真是神了，导致我以为难度是降序所以 T2 打完暴力就摆了。
贪一下就行了，只有两种情况，一种就是原数，另一种是原数的最高位减一，剩下全是 \(9\)。
末
状态还是不行，睡过头导致的。
明天开始还是早起去跑步吧。
放这套一眼全是数学的题估计就是为了让我们抓抓这个薄弱项，确实，菜就得多练。
完结撒花~
标签：aa,10,ch,bb,ll,bmatrix,CSP,模拟 From： https://www.cnblogs.com/Ratio-Yinyue1007/p/18328471