牛客 -330E Applese 涂颜色

题目

1
2
3
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld

题目描述

精通程序设计的 Applese 叕写了一个游戏。
在这个游戏中,有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大,你需要将答案对 $10^9+7$取模。

输入描述

1
仅一行两个正整数 n, m,表示方阵的大小。

输出描述

1
输出一个正整数,表示方案数对10^9+7取模。

示例1

输入

1
1 1

输出

1
2

示例2
输入

1
2 2

输出

1
4

备注

$1\leq n,m\leq10^{100000}$

题解

一个比较显然的结论是,对于每一列,有$2^n$种涂色方法。
我们可以发现,当确定了第一列之后,由于左右相邻不能同色,所以后面每一列的涂色方案也随之确定。因此答案就是 $2^n$

首先n的数字范围非常大,10的10万次方,所以数据一定是用字符串读进去的,其次,因为 n 很大,循环n次肯定超时。所以得降幂,费马小定理或者欧拉降幂都可以。

费马小定理

费马小定理:对于素数 $m$ 任意不是 $m$ 的倍数的 $b$,都有:$b^{m-1}\equiv1\ mod \ m$

  1. 先决条件成立:$10^9+7$是素数,$gcd(10^9+7, \ 2)=1$

  2. 处理:

    因$b^{m-1}=1$,故我们只需要算出除去1的部分有多少就行了,于是有

    $2^{n}=2^{n\%(m-1)}$ (m为$10^9+7$)

    这样n就减少了,但是$10^9+7$还是很大,要用到快速幂取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*
提交时间:2019-02-05 14:59:46 语言:C++ 代码长度:565 运行时间: 4 ms 占用内存:864K
运行状态:答案正确
*/
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
ll mod_pow(ll x, ll n) //快速幂
{
ll ans = 1;
while(n)
{
if(n&1)
ans = ans * x % MOD;
x = x*x % MOD;
n >>=1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

string s1, s2;
cin >> s1 >> s2;
ll p = 0;
ll len = s1.size();
for(int i = 0; i < len; i++)
p = (p*10 + s1[i] - '0') % (MOD - 1); //将读入的字符变成整数,并且这个过程中取模
cout << mod_pow(2, p) << endl;
return 0;
}

欧拉降幂

故有

$2^nmod\ m=2^{n\ mod\ \varphi(m)+\varphi(m)}\ mod\ m$

所以

  1. 先求出$ \varphi(m)$
  2. 再用快速幂求出$2^n$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*
提交时间:2019-02-05 16:38:55 语言:C++ 代码长度:855 运行时间: 8 ms 占用内存:916K
运行状态:答案正确
*/
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
ll mod_pow(ll x, ll n) //快速幂
{
ll ans = 1;
while(n)
{
if(n&1)
ans = ans * x % MOD;
x = x*x % MOD;
n >>=1;
}
return ans;
}

ll euler(ll n) //求phi
{
ll res = n;
for (ll i = 2; i*i <= n; i++)
if (n%i == 0)
{
res =res/i*(i-1);
while(n%i == 0)
n /= i;
}
if (n > 1)
res = res/n*(n-1);
return res;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

string s1, s2;
cin >> s1 >> s2;
ll p = euler(MOD);
ll len = s1.size();
ll ans = 0;
for(int i = 0; i < len; i++)
ans = (ans*10 + s1[i] - '0') % p; //算出n mod phi(m),phi:欧拉函数
ans += p; //算出n mod phi(m) + phi(m)
cout << mod_pow(2, ans) << endl;
return 0;
}