Codeforces Round #330 Div. 2 Prob. B. Pasha and Phone
問題：http://codeforces.com/contest/595/problem/B
解けなかったのでブログに書いておく。
各ブロックが、biで始まらないかつaiで割り切れる数字で構成される組み合わせの数え上げ（のMOD）。
→各ブロックを条件の通りで数えた後掛け算してmodするだけ
解けなかったのはstlのpowの返り値がdoubleだということに気付かなかったから。
powはなんとなく避けてた気がするけどなんでだっけな～→使ってみる→サンプル通るやんオッケーやん→WA→なんでや・・・
終わった後もWA出し続けて22回。ローカルとサーバーでの解が違っていて気付いた。
ついでに二分累乗法でよろしくやってくれるbinpowを書いた。
#include <iostream>
#include <string>
#include <vector>
#include <limits>
using namespace std;
template<class T = long long>
T binpow(T a, int n, T mod=std::numeric_limits<T>::max()){
if(n==0){
return 1;
}else if(n%2==1){
return (binpow(a,n-1)*a)%mod;
}else{
T b = binpow(a,n/2);
return (b*b)%mod;
}
}
constexpr long long MOD = 1e9+7;
int main() {
cin.tie(nullptr); ios::sync_with_stdio(false);
long long n,k,n_k;
cin >> n >> k;
n_k = n/k;
vector<long long> a(n_k,0),b(n_k,0);
for(int i = 0; i < n_k; ++i){
cin >> a[i];
}
for(int i = 0; i < n_k; ++i){
cin >> b[i];
}
long long nine_k = binpow(10,k)-1; //10^k - 1
long long ten_l=binpow(10,k-1); //10^(k-1)
long long ans=1;
for(int i = 0; i < n_k; ++i){
long long probs = nine_k/a[i]+1; //probabilities
long long b_minc = ten_l*b[i];
if(b_minc%a[i] != 0) b_minc += a[i]-b_minc%a[i];
long long b_maxc = ten_l*(b[i]+1)-1;
long long diff = (b_maxc<b_minc) ? 0 : (b_maxc-b_minc)/a[i] + 1;
probs-=diff;
ans = (ans*probs)%MOD;
}
cout << ans << endl;
return 0;
}5 5
2
0
>>> 45000