BZOJ2326 [HNOI2011]数学作业(分块矩阵快速幂)

题意：

定义函数Concatenate (1 ..N)是将所有正整数 1, 2, …, N 顺序连接起来得到的数，如concatenate(1..5)是12345，求concatenate(1...n)%m的值

思路：

矩阵快速幂，公式为

$$
\left[
\begin{matrix}
f(n)\\n\\1
\end{matrix}
\right]=
\left[
\begin{matrix}
10^k&1&1\\
0&1&1\\
0&0&1
\end{matrix}
\right]
\left[
\begin{matrix}
f(n-1)\\n-1\\1
\end{matrix}
\right]
$$

其中$10^k$可以分快处理，分n为0~9,10~99,100~999等

代码：

/**************************************************************

    Problem: 2326

    User: wrjlinkkkkkk

    Language: C++

    Result: Accepted

    Time:64 ms

    Memory:1292 kb

****************************************************************/

#include<iostream>

#include<iomanip>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#include<list>

#define fst first

#define sc second

#define pb push_back

#define mp(a,b) make_pair(a,b)

#define mem(a,b) memset(a,b,sizeof(a))

#define lson l,mid,root<<1

#define rson mid+1,r,root<<1|1

#define lc root<<1

#define rc root<<1|1

#define lowbit(x) ((x)&(-x))

#pragma Gcc optimize(2)

using namespace std;

typedef double db;

typedef long double ldb;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> PI;

typedef pair<ll,ll> PLL;

const int maxn =  + ;

const int maxm = 5e3 + ;

const double eps = 1e-;

const int inf = 0x3f3f3f3f;

const double pi = acos(-1.0);

int scan(){

    int res=,ch,flag=;

    if((ch=getchar())=='-')

        flag=;

    else if(ch>=''&&ch<='')

        res=ch-'';

    while((ch=getchar())>=''&&ch<='')

        res=res*+ch-'';

    return flag?-res:res;

}

ll n, m;

ll mul(ll x,ll y){

    ll s=;

    while(y)

    {

        if(y&)s=(s+x)%m;

        x=(x<<)%m;

        y>>=;

    }

    return s;

}

void mtpl(ll a[][], ll b[][],ll s[][]){

    ll tmp[][];

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

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

            tmp[i][j]=;

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

                tmp[i][j] += mul(a[i][k] , b[k][j])%m;

            }

        }

    }

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

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

            s[i][j] = tmp[i][j];

        }

    }

    return;

}

ll b[][];

void Fast_power(ll t,ll last){

    ll a[][];

    mem(a, );

    a[][] = t;

    a[][] = a[][] = a[][] = a[][] = a[][] = ;

    ll y = last-t/+;

    while(y){

        if(y & ) mtpl(b, a, b);

        mtpl(a, a, a);

        y >>= ;

    }

    //prt(ans);

    return;

}

int main(){

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

    mem(b, );

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

    ll t = ;

    while(t <= n){

        Fast_power(t, t-);

        t*=;

    }

    Fast_power(t,n);

    printf("%lld", b[][]%m);

    return ;

}

/*

8 3287492749272074

*/

巴特西

BZOJ2326 [HNOI2011]数学作业(分块矩阵快速幂)

最新文章

热门文章