AtCoder Beginner Contest 178 C

Beginner Contest 178 C"/>

AtCoder Beginner Contest 178 C

文章目录

• 题目
• 错误点
• 代码

题目

AtCoder Beginner Contest 178 C - Ubiquity

错误点

• 未考虑数据大小，没使用long long。
• 运行时间过长，未用快速幂。
• 公式计算错误，没有想到容斥原理这一知识点。
• 最后未加 MOD（=1e9+7）再模 MOD，从而导致部分答案出现负数。

代码

#include<iostream>
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;//快速幂模板 （a的b次方并模MOD）
ll binaryPow(ll a, ll b) {ll sum = 1;while (b > 0) {if (b & 1) {sum = ((sum%MOD)*(a%MOD)) % MOD;}a = ((a%MOD)*(a%MOD))% MOD;b >>= 1;}return sum;
}int main(){ll n=0,ans=0;while(cin>>n){	//计算公式：10^n-2*(9^n)+8^nans=((binaryPow(10,n))%MOD-2*binaryPow(9,n)%MOD+binaryPow(8,n)%MOD+MOD)%MOD;//最后注意加MOD再模MODcout<<ans<<endl;	}return 0;
}