题目
Description
横一划竖一划, 横一划竖一划............ 小 R 画出了一个 n*m 的棋盘.
由于 NOIP 快要到了, 小 R 有了一个奇妙的想法.
在棋盘的每一个小方格中填入 N,O,I,P 这 4 个字母中的一个, 若棋盘中每一个 2*2 的小棋盘中都有 N,O,I,P 这 4 个字母, 小 R 就认为这个棋盘是幸运棋盘. 小 R 想知道一共有多少种不同的幸运棋盘. 由于这个结果可能会很大, 你只需输出对 1,000,000,007 取模后的值.
Input
两个整数 n,m 表示棋盘的大小.
Output
一个整数表示幸运棋盘的个数对 1,000,000,007 取模后的值.
- Sample Input
- 2 3
- Sample Output
- 48
- Data Constraint
- Hint
对于 30% 的数据, n,m≤10
对于 70% 的数据, n,m≤1,000,000
对于 100% 的数据, 2≤n,m≤2,000,000,000
分析
显然, 我们先以 2*2 为起点每向下就 * 2, 向左 * 2
所为这样下来就会出现限定数, 所以不用管
然后就去开始重复的 24
代码
- #include<iostream>
- #define mod 1000000007
- using namespace std;
- long long ksm(long long a,long long b)
- {
- long long x=a,ans=1;
- while (b)
- {
- if (b&1!=0) ans=ans*x%mod;
- x=x*x%mod;
- b>>=1;
- }
- return ans%mod;
- }
- int main ()
- {
- long long n,m;
- cin>>n>>m;
- long long a=ksm(2,n-1),b=ksm(2,m-1);
- cout<<(a+b-2)*12%mod;
- }
来源: http://www.bubuko.com/infodetail-3113384.html