HDU6395 Sequence(矩阵快速幂+数论分块)

题意：

F(1)=A，F(2)=B，F(n)=C*F(n-2)+D*F(n-1)+P/n

给定ABCDPn，求F(n) mod 1e9+7

思路：

P/n在一段n里是不变的，可以数论分块，再在每一段里用矩阵快速幂

debug了一下午。。

坑点：

1.数论分块的写法要注意，已更新

2.矩阵乘法在赋值回去的时候记得模一下

3.矩阵相乘不可逆，注意看一下

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<string>

#include<stack>

#include<queue>

#include<deque>

#include<set>

#include<vector>

#include<map>

#include<functional>

#define fst first

#define sc second

#define pb push_back

#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)) 

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 db eps = 1e-;

const int mod = 1e9+;

const int maxn = 2e6+;

const int maxm = 2e6+;

const int inf = 0x3f3f3f3f;

const db pi = acos(-1.0);

void prt(ll b[][]){

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

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

            printf("%3I64d ", b[i][j]);

        }

        printf("\n");

    }

    return;

}

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

    ll tmp[][];

    mem(tmp, );

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

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

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

                tmp[i][j] += (a[i][k]*b[k][j])%mod;

            }

        }

    }

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

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

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

        }

    }

    return;

}ll a, b, c, d, p, n;

ll B[][];

void fp(ll n, ll tmp){

    ll A[][];

    mem(A, );

    A[][] = d;

    A[][] = c;

    A[][] = ;

    A[][] = tmp;

    A[][] = ;

    //prt(A);

    while(n){

        if(n&) mtpl(A,B,B);

        mtpl(A,A,A);

        n>>=;

    }

    return;

}

int main() {

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%I64d %I64d %I64d %I64d %I64d %I64d", &a, &b, &c, &d, &p, &n);

        if(n==){

            printf("%I64d\n", a);

            continue;

        }

        if(n==){

            printf("%I64d\n", b);

            continue;

        }

        mem(B, );

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

        B[][] = b;

        B[][] = a;

        B[][] = ;

        ll l , r;

        for(l = , r = ; l <= n; l = r + ){

            if(p/l) r = min(p, p/(p/l));

            else r = n;

            ll tmp = p/l;

            fp(r-l+,tmp);

        }

        printf("%I64d\n", B[][]);

    }

    return ;

}

/*

4

1 2 1 2 5 3

1 2 1 2 3 5

1 2 3 4 7 4

2 3 3 3 3 4

 */

巴特西

HDU6395 Sequence(矩阵快速幂+数论分块)

最新文章

热门文章