Dwarfs have planted a very interesting plant, which is a triangle directed "upwards". This plant has an amusing feature. After one year a triangle plant directed "upwards" divides into four triangle plants: three of them will point "upwards" and one will point "downwards". After another year, each triangle plant divides into four triangle plants: three of them will be directed in the same direction as the parent plant, and one of them will be directed in the opposite direction. Then each year the process repeats. The figure below illustrates this process.
Help the dwarfs find out how many triangle plants that point "upwards" will be in n years.
The first line contains a single integer n (0 ≤ n ≤ 1018) — the number of full years when the plant grew.
Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, coutstreams or the %I64d specifier.
Print a single integer — the remainder of dividing the number of plants that will point "upwards" in n years by1000000007 (109 + 7).
1
3
2
10
The first test sample corresponds to the second triangle on the figure in the statement. The second test sample corresponds to the third one.
题意:
给出 n(0 ~ 10 ^ 18),代表一个正方形经过 n 次的切割后,得到正三角形的个数是多少。
思路:
矩阵快速幂。递推式子:
Ui+1 = 3 X Ui + Di;
Di+1 = Ui + 3 X Di;得出的矩阵就不给出了。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef long long ll; typedef vector<ll> vec; typedef vector<vec> mat; const ll MOD = 1000000007; mat mul (mat a, mat b) { mat c(a.size(), vec(b[0].size())); for (int i = 0; i < a.size(); ++i) { for (int j = 0; j < b[0].size(); ++j) { for (int k = 0; k < b.size(); ++k) { c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % MOD; } } } return c; } mat pow (mat a, ll n) { mat b(a.size(), vec(a[0].size())); for (int i = 0; i < a.size(); ++i) b[i][i] = 1; while (n > 0) { if (n & 1) b = mul(b, a); a = mul(a, a); n >>= 1; } return b; } int main() { ll n; while (~scanf("%I64d", &n)) { mat a(2, vec(2)); a[0][0] = a[1][1] = 3; a[0][1] = a[1][0] = 1; a = pow(a, n); printf("%I64d\n", a[0][0]); } return 0; }
相关推荐
Codeforces 185A - Plant 全测试点49个
plant simulation基础培训教程(中文),含实例,对plant simulation菜单进行了基础性的介绍,适合新手快速掌握软件。
周金平plantsimulation教程
Plant Simulation案例合计,八十几页全是英文。看自己需不需要
Plant Simulation编程语言SimTalk2.0官方说明_公众号@仿真社区Plant Simulation1
Tecnomatix Plant Simulation教学 生产、物流仿真教学
学习 Plant Simulation 的资料
解决adams_plant问题
eM-Plant 仿真软件学习必不可少 很适合初学者用额
一个简单的入门级别的plant simulation案例
em-plant仿真软件初学者必备 同过一个实例一步一步教你使用em-plant
3d设计工程图浏览软件,Smart plant review
介绍Siemens Plant simulation的基本使用,快速掌握操作。
plant simulation初学者都会为英文版的帮助文件烦恼,这里提供一本翻译后的软件功能更新说明,仅供大家学习交流
Siemens Plant Simulation
Plant Simulation应用教程[周金平][程序源代码]
最好的关于CAD Plant 3D 的学习资料,值得爱好者下载学习!
eM-Plant一些方法技巧以及操作软件的一些技巧
基于Plant Simulation的自动化立体库效能分析究.rar
Plant Proteomics Methods and Protocols —————————————————————————— The aim of Plant Proteomics: Methods and Protocols is to present up-to- date methods and protocols used by ...