A simple Blog for wyx I've been down the bottle hoping.
BZOJ 4002 有意义的字符串 数学 矩阵乘法
发表于: | 分类: Oi | 评论:0 | 阅读:64

集训队题一年比一年不可做,先回头写写吉林省选吧

这题求的是$\lfloor (\frac{b+\sqrt{d}}{2})^n \rfloor$

看到$\frac{b+\sqrt{d}}{2}$就容易想到$\frac{b-\sqrt{d}}{2}$,我们令 $f(i)=(\frac{b+\sqrt{d}}{2})^n+(\frac{b-\sqrt{d}}{2})^n$

容易知道$x^n+y^n=(x^{n-1}+y^{n-1})(x+y)-xy(x^{n-2}+y^{n-2})$

所以$f(i)=b\times f(i-1)+\frac{d-b^2}{4}f(i-2)$

这个式子显然可以矩阵乘法算一下

然后看一下这个式子$\frac{b-\sqrt{d}}{2}$,题目里面给了$b^2 \leq d \leq (b+1)^2$

所以有$b \leq \sqrt{d}, b - \sqrt{d} \leq 0$

而且这个数的绝对值肯定$<1$

分类讨论一下,看看是否会-1就行了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const ull mod = 7528443412579576937ll;

ull mul(ull a,ull b){
    ull res = 0; a %= mod;
    for(;b;b>>=1,a=(a+a)%mod)
        if(b&1)
            res = (res + a) % mod;
    return res;
}

struct Maxtrix{
    ull a[2][2];

    Maxtrix () {
        memset(a,0,sizeof a);
    } 

    void init(){
        a[0][0] = a[1][1] = 1ll;
    }

    void show(){
        cout << a[0][0] << " " << a[0][1] << endl;
        cout << a[1][0] << " " << a[1][1] << endl;
    }

}tmp1,tmp2;

Maxtrix operator * (const Maxtrix &a,const Maxtrix &b){
    Maxtrix res; int i,j,k;
    for(i=0;i<2;++i)
        for(j=0;j<2;++j)
            for(k=0;k<2;++k)
                (res.a[i][j] += mul(a.a[i][k],b.a[k][j]) ) %= mod;
    return res;
}

Maxtrix pow(Maxtrix a,ull b){
    Maxtrix res; res.init();
    for(;b;b>>=1,a=a*a)
        if(b&1)
            res = res * a;
    return res;
}

int main(){
    ull b,d,n;
    cin >> b >> d >> n;
    if(n == 0) {
        puts("1");
        return 0;
    }
    tmp1.a[0][0] = b, tmp1.a[0][1] = 2;
//  tmp1.show();
    tmp2.a[0][0] = b, tmp2.a[0][1] = 1, tmp2.a[1][0] = (d-b*b)/4, tmp2.a[1][1] = 0;
//  tmp2.show();
    tmp2 = pow(tmp2,n-1);
    tmp1 = tmp1 * tmp2;
    ull ans = tmp1.a[0][0];
    if(n%2==0 && d != mul(b,b)) ans = (ans - 1 + mod) % mod;
    cout << ans << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP