1922.
看到这个题号就想哈秋哈秋哈秋
练习power加速
还是数数儿
不过1e15很大要mod
直接开power会overflow
一个一个数会TLE
#
我记得好像可以shift就不用dpㄌ
不过我比较笨==
连dp都没开 多做很多重复的事
#
原本用ee跟oo纪录现在分别做了几个
后来改直接一起5*4=20
using ll = long long;
class Solution {
public:
int countGoodNumbers(long long n) {
ll mod = 1e9 + 7;
ll cnt = 1;
bool even_end = n % 2;
ll half = n / 2;
while(half > 0){
ll ee = 1, ect = 20;
while(ee * 2 <= half){
ee *= 2;
ect = (ect * ect) % mod;
}
half -= ee;
cnt = (cnt * ect) % mod;
}
if(even_end) cnt = (cnt * 5) % mod;
return cnt;
}
};