【bzoj4002】[JLoi2015]有意义的字符串

2015.04.20 20:31 Mon | 26次阅读 | 旧日oi | 固定链接 | 源码

Description

B君有两个好朋友,他们叫宁宁和冉冉。
有一天,冉冉遇到了一个有趣的题目:输入 b, d, n,求
(b+d√2)n
的整数部分。
她拿着题目去问宁宁,宁宁说:我有一个绝妙的做法,可惜硬盘太小,存不下。
这时 B君看到了题目,他觉得宁宁说的有道理,硬盘确实存不下,他说那我们就来求模7528443412579576937之后的结果吧。

Input

一行三个整数 b, d, n。

Output

一行一个数表示模 7528443412579576937之后的结果。

Sample Input

Input I: 1 5 9 Input II: 11 125 6715504

Sample Output

Output I: 76 Output II: 1499928102740042526

HINT

【数据规模与约定】
对于 100%的数据,0<b2<=d<(b+1)2<=1018。
对于 100%的数据,b mod 2=1,d mod 4=1,n<=1018。
对于 40%的数据,b<100, n<6。
对于另 20%的数据,b=1, d=5。

题解

我是第一个A的!!!!
先不要管各种数字有什么意义……虽然的确很有意思。。
我们观察式子的形式,发现这有点像形如xn=bxn-1+cxn-2这种数列的特征根,于是我们考虑将式子补上一项((b-√d)/2)^n,变成一个通项公式。补上这项有一个特点,就是绝对值永远小于1,所以我们可以将两部分一起算,最后根据n的奇偶决定是否-1就可以。
变成了数列的通项公式之后,我们可以转化为形如xn=bxn-1+cxn-2这种递推形式,c就是(d-b*b)/4;
于是我们就可以用矩阵乘法搞了。
前两项分别把n=1和n=2带入通项公式就行了
取模数太大,要用快速乘

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
typedef unsigned long long ll;
const ll mod = 7528443412579576937ll;
using namespace std;
ll b,d,n,c;
struct Matrix{
    ll m[2][2];
}ans,mul,tmp;
ll qmul(ll x,ll k)
{
    ll ret=0;
    while(k)
    {
        if(k&1) ret=(ret+x)%mod;
        k>>=1;
        x=(x+x)%mod;
    }
    return ret;
}
Matrix operator *(Matrix a,Matrix b)
{
    Matrix c;memset(&c,0,sizeof(c));
    for(int i=0;i<2;i++)
    for(int j=0;j<2;j++)
    for(int k=0;k<2;k++)
    c.m[i][j]=(c.m[i][j]+qmul(a.m[i][k],b.m[k][j]))%mod;
    return c;
}
int main()
{
    scanf("%llu%llu%llu",&b,&d,&n);
    if(n==0) 
    {
        puts("1");
        return 0;
    }
    int t=0;
    if(n%2==0) t=1; 
    n-=2;
    ans.m[0][1]=b;ans.m[0][0]=(b*b+d)/2;
    mul.m[0][0]=b;mul.m[0][1]=1;mul.m[1][0]=(d-b*b)/4;
    tmp.m[0][0]=tmp.m[1][1]=1;
    while(n)
    {
        if(n&1) tmp=tmp*mul;
        n>>=1;
        mul=mul*mul;
    }
    ans=ans*tmp;
    printf("%llu\n",ans.m[0][0]-t);
    return 0;
}```