首頁 > 其他 > 詳細

洛谷P3263 [JLOI2015]有意義的字符串(數學+矩陣乘法)

時間:2019-06-28 15:27:29      閱讀:49      評論:0      收藏:0      [點我收藏+]

標簽:代碼   scan   name   ans   矩陣   ++   bits   class   spa   

寫篇題解紀念下,畢竟我一道題犯這么多SB錯誤(sizeof(0),long long傳參傳成int,沒有賦值等)也是不容易= =

考慮數列\(a_n=(\frac{b+\sqrt{d}}{2})^n+(\frac{b-\sqrt{d}}{2})^n\),則數列\(a_n\)的特征方程為\(x^2-bx-\frac{d-b^2}{4}=0\)

\(\{a_n\}\)的遞推公式為\(a_n=ba_{n-1}+\frac{d-b^2}{4}a_{n-2}\),邊界是\(a_0=2\),\(a_1=b\)

因為根據題目條件得\(4|d-b^2\),所以\(a_n\)為整數,所以\((\frac{b+\sqrt{n}}{2})^n+(\frac{b-\sqrt{n}}{2})^n\)為整數

又因為\(b^2 \leq d <(b+1)^2\),所以\(-1<\frac{b-\sqrt{d}}{2}\leq0\),很小的一個數,所以我們可以直接矩陣快速冪求出\(a_n\)再計算出答案

\(n\)為偶數且\(b^2\neq d\)時,\(0\leq(\frac{b-\sqrt{d}}{2})^n<1\),此時\(ans=a_n-1\)

其它情況,\(-1<(\frac{b-\sqrt{d}}{2})^n\leq 0\),此時\(ans=a_n\)

代碼:

#include <bits/stdc++.h>
#define ll long long
#define mod 7528443412579576937ll
using namespace std;

ll Mar[2][2],E[2][2],tmp[2][2];

inline ll add(ll x,ll y){ return x+y>=mod||x+y<0?x-mod+y:x+y; }
inline ll Minus(ll x,ll y){ return x-y<0?x-y+mod:x-y; }
inline ll qorg(ll x,ll y){
    ll d=(ll)(x*(long double)y/mod+0.5);
    return Minus(x*y,d*mod);
}
void mul(ll a[][2],ll b[][2]){
    memset(tmp,0,sizeof(tmp));
    for(int i=0;i<2;++i)
        for(int k=0;k<2;++k)
            for(int j=0;j<2;++j)
                tmp[i][j]=add(tmp[i][j],qorg(a[i][k],b[k][j]));
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            a[i][j]=tmp[i][j];
}
void qpow(ll x){ for(;x;x>>=1,mul(E,E)) if(x&1) mul(Mar,E); }

int main(){ 
    ll b,d,n;
    scanf("%lld%lld%lld",&b,&d,&n);
    Mar[0][0]=b,Mar[0][1]=2;
    E[0][0]=b,E[1][0]=(d-b*b)/4ll,E[0][1]=1;
    if(n==0){ puts("1");return 0; }
    qpow(n-1);
    if(n%2==0 && b*b!=d) Mar[0][0]=Minus(Mar[0][0],1);
    printf("%lld",Mar[0][0]%mod);
}

洛谷P3263 [JLOI2015]有意義的字符串(數學+矩陣乘法)

標簽:代碼   scan   name   ans   矩陣   ++   bits   class   spa   

原文:https://www.cnblogs.com/PsychicBoom/p/11102788.html

(0)
(0)
   
舉報
評論 一句話評論(0
登錄后才能評論!
? 2014 bubuko.com 版權所有 魯ICP備09046678號-4
打開技術之扣,分享程序人生!
             

魯公網安備 37021202000002號

湖南快乐十分钟走势图