$bzoj\ 2326$

题目大意

对给定的$n$，$m$，求$f_n=(10^{log_{10}(n)+1}f_{n-1}+n)\ mod \ m$。

解

题目大意就是方程。

$$ \mathbf{F(i)}= \left( \begin{array}{ccc} f_i & i & 1 \end{array} \right) $$

升序枚举$k=10^x \in (1,n)$，构造$\mathrm{R}$

$$ \mathrm{R}= \left( \begin{array}{ccc} k\ mod\ m & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{array} \right) $$

$$ n_0=0, \mathrm{F(0)}= \left( \begin{array}{c} 0 & 0 & 1 \end{array} \right) $$

分段求出$\mathrm{F(k-1)}$，即可求得$f_n$。

Code

#include <cstdio>
#include <cmath>
#include <cstring>
#define rep(i,x,y) for (int i=x; i<=y; ++i)

typedef long long ll;
struct mat
{
    int n,m;
    ll v[3][3];
    mat(){}
    mat(int a,int b):n(a),m(b)
    {
        memset(v,0,sizeof(v));
    }
    ll *operator [] (int x)
    {
        return v[x];
    }
} r=mat(2,2),s=mat(0,2),t;
ll n,m,mx;

inline void operator *= (mat &a,mat b)
{
    ll t[3];
    rep(i,0,a.n)
    {
        memset(t,0,sizeof(t));
        rep(j,0,a.m)
            rep(k,0,a.m)
                t[j]=(t[j]+a[i][k]*b[k][j]%m)%m;
        memcpy(a[i],t,sizeof(t));
    }
}

int main()
{
    scanf("%lld%lld",&n,&m),mx=log10(n)+1;
    r[0][0]=10%m,r[1][0]=r[2][0]=r[1][1]=r[2][1]=r[2][2]=s[0][2]=1;
    for (ll i=1,j=9; i<=mx; r[0][0]=r[0][0]*10%m,n-=j,j*=10,++i)
    {
        t=r;
        for (ll k=i<mx?j:n; k; k>>=1,t*=t)
            if (k&1)
                s*=t;
    }
    printf("%lld\n",s[0][0]);
    return 0;
}