【bzoj】2326 [HNOI2011]数学作业

【题意】给定n和m，求1~n从高位到低位连接%m的结果。n=11时，ans=1234567891011%m。n<=10^18，m<=10^9。

【算法】递推+矩阵快速幂

【题解】

考虑枚举位数个数k，对于不同的k单独递推，设f[i]表示1~i的答案，则有：

$$f_n=f_{n-1}*10^k+i$$

转化为矩阵递推式，则有：

$$\begin{vmatrix}10^k & 1 & 1\\ 0 & 1 & 1\\0 & 0 & 1\end{vmatrix} \times \begin{vmatrix}f_n \\ n\\1 \end{vmatrix}=\begin{vmatrix}f_{n+1}\\n+1\\1\end{vmatrix}$$

转化为幂形式，则有：

$$\begin{vmatrix}10^k & 1 & 1\\ 0 & 1 & 1\\0 & 0 & 1\end{vmatrix}^n \times \begin{vmatrix}f_i \\ i\\1 \end{vmatrix}=\begin{vmatrix}f_{i+n}\\i+n\\1\end{vmatrix}$$

分段进行矩阵快速幂即可。

注意读入的n是long long。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=;

int c[N][N],ANS[N][N],A[N][N],m;

ll n;///

void multply(int a[N][N],int b[N][N]){

    for(int i=;i<=;i++){

        for(int j=;j<=;j++){

            c[i][j]=;

            for(int k=;k<=;k++){

                c[i][j]=(c[i][j]+1ll*a[i][k]*b[k][j]%m)%m;

            }

        }

    }

    for(int i=;i<=;i++)for(int j=;j<=;j++)b[i][j]=c[i][j];

}

void solve(ll p,int &f,int x,int k){

    memset(A,,sizeof(A));

    A[][]=A[][]=A[][]=A[][]=A[][]=;A[][]=k;

    ANS[][]=f;ANS[][]=x%m;ANS[][]=;

    while(p){

        if(p&)multply(A,ANS);

        multply(A,A);

        p>>=;

    }

    f=ANS[][];

}

int main(){

    scanf("%lld%d",&n,&m);

    ll x=,y=;

    int k=%m,ans=;

    while(x+y<n){

        solve(y,ans,x%m,k);//

        x+=y;y*=;k=1ll*k*%m;

    }

    solve(n-x,ans,x%m,k);

    printf("%d",ans%m);

    return ;

}