jzoj3013. 【NOIP2012模拟10.6】填充棋盘

本文主要是介绍jzoj3013. 【NOIP2012模拟10.6】填充棋盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

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

Hint

对于30%的数据，n,m≤10

对于70%的数据，n,m≤1,000,000

对于100%的数据，2≤n,m≤2,000,000,000

分析

不难推出2*2的棋盘有24种摆法

2*3有48

2*4有96

……

每增加一行或一列摆法就会*2

但由于左上角的2*2的棋盘是重复记录的，所以最后还要再减24

得出规律 ans=24*（2^n-2+2^m-2-1）

但由于数据过大（2≤n,m≤2,000,000,000），如果一个一个乘会超时，所以要用快速幂。

CODE

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const long long mo=1000000007;
long long n,m,ans;long long pow(long long b) {long long ans=1,x=2;while (b!=0) {if (b&1!=0)ans=(ans*x)%mo;x=(x*x)%mo;b>>=1;}return ans;
}int main(){scanf("%d%d",&n,&m);ans=(pow(n-2)+pow(m-2))%mo;ans=(ans*24-24)%mo;printf("%d\n",ans);return 0;
}

这篇关于jzoj3013. 【NOIP2012模拟10.6】填充棋盘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---