題意：給定一個(gè)大三角形，然后每次按照?qǐng)D片分割成4個(gè)小三角形，問(wèn)n次后有多少個(gè)向上的三角形。

思路：矩陣快速冪，可以發(fā)現(xiàn)，每一個(gè)向上的的可以在下一次產(chǎn)生3個(gè)向上的，1個(gè)向下的，向下的每次可以產(chǎn)生一個(gè)向上的和三個(gè)向下的。這剛好是矩陣的應(yīng)用。注意0的情況。

code：

#include <bits/stdc++.h> using namespace std;typedef long long ll; const ll mod=1e9+7;struct node {ll v[5];node (){v[1]=3;v[2]=1;v[3]=1;v[4]=3;}node mul(node t){node p;p.v[1]=(v[1]*t.v[1]+v[2]*t.v[3])%mod;p.v[2]=(v[1]*t.v[2]+v[2]*t.v[4])%mod;p.v[3]=(v[3]*t.v[1]+v[4]*t.v[3])%mod;p.v[4]=(v[3]*t.v[2]+v[4]*t.v[4])%mod;return p;}void print(){cout<<v[1]<<" "<<v[2]<<endl;cout<<v[3]<<" "<<v[4]<<endl;} };node mi(node k,ll n) {if (n==1) return k;node t=mi(k,n/2);//t.print();t=t.mul(t);// t.print();if (n%2==1) t=t.mul(k);return t; }int main() {ll n;cin>>n;if (n==0) {puts("1");return 0;}node t;t=mi(t,n);cout<<t.v[1]%mod<<endl; }

總結(jié)

以上是生活随笔為你收集整理的codeforce 185 A——Plant的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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