牛客 -330E Applese 涂颜色
题目
1 2 3
| 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32768K,其他语言65536K 64bit IO Format: %lld
|
题目描述
精通程序设计的 Applese 叕写了一个游戏。
在这个游戏中,有一个 n 行 m 列的方阵。现在它要为这个方阵涂上黑白两种颜色。规定左右相邻两格的颜色不能相同。请你帮它统计一下有多少种涂色的方法。由于答案很大,你需要将答案对 $10^9+7$取模。
输入描述
输出描述
示例1
输入
输出
示例2
输入
输出
备注
$1\leq n,m\leq10^{100000}$
题解
一个比较显然的结论是,对于每一列,有$2^n$种涂色方法。
我们可以发现,当确定了第一列之后,由于左右相邻不能同色,所以后面每一列的涂色方案也随之确定。因此答案就是 $2^n$
首先n的数字范围非常大,10的10万次方,所以数据一定是用字符串读进去的,其次,因为 n 很大,循环n次肯定超时。所以得降幂,费马小定理或者欧拉降幂都可以。
费马小定理
费马小定理:对于素数 $m$ 任意不是 $m$ 的倍数的 $b$,都有:$b^{m-1}\equiv1\ mod \ m$
先决条件成立:$10^9+7$是素数,$gcd(10^9+7, \ 2)=1$
处理:
因$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
|
#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$
所以
- 先求出$ \varphi(m)$
- 再用快速幂求出$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
|
#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) { 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; ans += p; cout << mod_pow(2, ans) << endl; return 0; }
|