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;
}
};