佛山高端网站制作,地方门户,WordPress网站被恶意登录,怎么模板建站题意#xff1a;给定一个大三角形#xff0c;然后每次按照图片分割成4个小三角形#xff0c;问n次后有多少个向上的三角形。 思路#xff1a;矩阵快速幂#xff0c;可以发现#xff0c;每一个向上的的可以在下一次产生3个向上的#xff0c;1个向下的#xff0c;向下的每…题意给定一个大三角形然后每次按照图片分割成4个小三角形问n次后有多少个向上的三角形。 思路矩阵快速幂可以发现每一个向上的的可以在下一次产生3个向上的1个向下的向下的每次可以产生一个向上的和三个向下的。这刚好是矩阵的应用。注意0的情况。 code #include bits/stdc.h
using namespace std;typedef long long ll;
const ll mod1e97;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(){coutv[1] v[2]endl;coutv[3] v[4]endl;}
};node mi(node k,ll n)
{if (n1) return k;node tmi(k,n/2);//t.print();tt.mul(t);// t.print();if (n%21) tt.mul(k);return t;
}int main()
{ll n;cinn;if (n0) {puts(1);return 0;}node t;tmi(t,n);coutt.v[1]%modendl;
}
