題目鏈接：點(diǎn)擊查看

題意：字符串S僅由'c'和'f'組成，滿足S[i]=S[i-1]+S[i-2]，求每?jī)蓚€(gè)c之間的距離之和。

解析：題目不難懂，主要是這是一個(gè)非線性遞推，因?yàn)閯倢W(xué)會(huì)了暴力求解線性方程的系數(shù)，所以迫不及待的暴力求出了前10項(xiàng)的值，然后套用for循環(huán)來求系數(shù)，當(dāng)然結(jié)果就是白白浪費(fèi)了時(shí)間。

當(dāng)然，既然字符串S滿足斐波那契數(shù)列的規(guī)律，那么我們也可以從這里入手，大膽假設(shè)結(jié)果與前兩項(xiàng)有關(guān)系。

網(wǎng)上的大多數(shù)方法我都沒看懂。。主要是寫的太抽象了，我想不過來（還是太笨了）

這里說一下兩個(gè)方法，一個(gè)是昨天上課的時(shí)候一個(gè)大佬同學(xué)講的，還有一個(gè)是從網(wǎng)上看到的比較好的方法，廢話不多說，直接切入正題：

方法一：利用平均值

首先我們需要四個(gè)輔助數(shù)組，分別是len，num，dis和sum，分別代表：字符串長(zhǎng)度、字符串中'c'的個(gè)數(shù)、每一個(gè)'c'到達(dá)字符串左端的距離和、結(jié)果。

根據(jù)字面意思，很容易就能推出len和num的公式，都是斐波那契數(shù)列：

len[i]=len[i-1]+len[i-2];

num[i]=num[i-1]+num[i-2];

然后是dis，可以知道，S[i]字符串是由S[i-2]與S[i-1]拼合而成，所以原來S[i-2]中的'c'點(diǎn)到左端的距離不變，仍為dis[i-2]，而S[i-1]中的num[i-1]個(gè)'c'點(diǎn)到左端的距離均多了len[i-2]的長(zhǎng)度，故可以推出：

dis[i]=dis[i-2]+dis[i-1]+len[i-2]*num[i-1];

最后就是利用平均值求一下sum的關(guān)系了，首先，易知S[i]=S[i-1]+S[i-2]+？，那么關(guān)鍵就是對(duì)？的求解。

其中，？代表的是S[i-2]與S[i-1]交叉部分的距離和。

我們先將S[i]分解為S[i-2]和S[i-1]兩個(gè)部分，以下簡(jiǎn)稱為左端與右端，那么每一個(gè)左端的點(diǎn)到右端的點(diǎn)的距離和，可以轉(zhuǎn)換為左端的點(diǎn)的平均值到右端的點(diǎn)的平均值的距離，然后乘以左端的點(diǎn)和右端的點(diǎn)的數(shù)量的乘積，表示由這么多條路線可行，想一想是不是？

sum[i]=sum[i-1]+sum[i-2]+(dis[i-1]/num[i-1]-dis[i-2]/num[i-2]+len[i-2])*num[i-1]*num[i-2];

這里還需要優(yōu)化一下，因?yàn)楣街袔е?#xff0c;會(huì)丟失精度，所以我們將公式展開，可以得到最終的形式：

sum[i]=sum[i-1]+sum[i-2]+dis[i-1]*num[i-2]-dis[i-2]*num[i-1]+len[i-2]*num[i-1]*num[i-2];

注意：當(dāng)處理減號(hào)時(shí)，記得加mod再減去mod，防止負(fù)數(shù)取模出現(xiàn)異常錯(cuò)誤。

上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=202314;const int mod=530600414;LL len[N],num[N],sum[N],dis[N];//len：長(zhǎng)度，num：c的個(gè)數(shù)，sum：結(jié)果，dis：所有c到左端的距離和void init() {len[1]=1;len[2]=2;num[1]=1;num[2]=0;for(int i=3;i<N;i++){len[i]=(len[i-1]+len[i-2])%mod;num[i]=(num[i-1]+num[i-2])%mod;}sum[1]=0;sum[2]=0;dis[1]=0;dis[2]=0;sum[3]=0;sum[4]=0;sum[5]=5;for(int i=3;i<N;i++){dis[i]=((dis[i-1]+dis[i-2])%mod+(len[i-2]*num[i-1])%mod)%mod;}for(int i=6;i<N;i++){sum[i]=(sum[i-1]+sum[i-2]+((dis[i-1]*num[i-2])%mod-(dis[i-2]*num[i-1])%mod+mod)%mod+((len[i-2]*num[i-1])%mod*num[i-2])%mod)%mod;} }int main() { // freopen("input.txt","r",stdin);int w;init();cin>>w;int kase=0;while(w--){int n;scanf("%d",&n);printf("Case #%d: %lld\n",++kase,sum[n]);}return 0; }

---

方法二：利用中點(diǎn)

這個(gè)方法需要借助五個(gè)輔助數(shù)組，分別是：len，num，dis，dis2和sum，其余四個(gè)與上述方法的意義相同，而dis2代表的與dis恰好相反，即每一個(gè)'c'到達(dá)字符串左端的距離和

這個(gè)方法比較好理解，仍然是將S[i]分為左右兩個(gè)部分，然后左端的點(diǎn)到右端的距離和乘右端的點(diǎn)的數(shù)量，加上右端的點(diǎn)到左端的距離和乘左端的點(diǎn)的數(shù)量，就是？所表示的了。光看文字描述可能有些抽象，轉(zhuǎn)換成公式再看一遍可能就好很多了：

sum[i]=sum[i-1]+sum[i-2]+dis2[i-2]*num[i-1]+dis[i-1]*num[i-2];

這個(gè)方法的好處就是不用擔(dān)心會(huì)出現(xiàn)負(fù)數(shù)，從而取模異常的情況。

有個(gè)小細(xì)節(jié)需要處理：就是關(guān)于dis和dis2數(shù)組，如果dis是從0開始計(jì)數(shù)，則dis2需要從1開始計(jì)數(shù)，反之亦然，因?yàn)榉乐怪貜?fù)計(jì)數(shù)。好了，上代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=202314;const int mod=530600414;LL len[N],num[N],sum[N],dis[N],dis2[N];//len：長(zhǎng)度，num：c的個(gè)數(shù)，sum：結(jié)果，dis：所有c到左端的距離和，dis2：所有c到右端的距離和 void init() {len[1]=1;len[2]=2;num[1]=1;num[2]=0;for(int i=3;i<N;i++){len[i]=(len[i-1]+len[i-2])%mod;num[i]=(num[i-1]+num[i-2])%mod;}sum[1]=0;sum[2]=0;dis[1]=0;dis[2]=0;dis2[1]=1;dis2[2]=0; sum[3]=0;sum[4]=0;sum[5]=5;for(int i=3;i<N;i++){dis[i]=((dis[i-1]+dis[i-2])%mod+(len[i-2]*num[i-1])%mod)%mod;dis2[i]=((dis2[i-1]+dis2[i-2])%mod+(len[i-1]*num[i-2])%mod)%mod;}for(int i=6;i<N;i++){sum[i]=((sum[i-1]+sum[i-2])%mod+(dis[i-1]*num[i-2])%mod+(dis2[i-2]*num[i-1])%mod)%mod;} }int main() { // freopen("input.txt","r",stdin);int w;init();cin>>w;int kase=0;while(w--){int n;scanf("%d",&n);printf("Case #%d: %lld\n",++kase,sum[n]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 5459 Jesus Is Here(思维+非线性递推)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。