No.147 試験監督(2) - yukicoder
- 繰り返し2乗法を使うもんだい。フィボナッチ数列が隠れているとは...
- 行列繰り返し2乗法で高速化できないか?というのはテクニックとして覚えておこう。(蟻本で見てはいたんだけどなぁ...)
const ll Mod = (int)(1E+9)+7;
class Invigilator2 {
public:
ll tenPow(ll a, string k) {
reverse(RANGE(k));
ll ret = 1LL;
ll prev = a;
for (auto c : k)
{
ll cur = 1LL;
ll ten = 1LL;
REP(i,c-'0')
(cur *= prev) %= Mod;
(ret *= cur) %= Mod;
REP(i,10)
(ten *= prev) %= Mod;
prev = ten;
}
return ret;
}
typedef array<ll,4> Mat;
Mat mul(const Mat &a, const Mat &b) {
return Mat{(a[0]*b[0]%Mod+a[1]*b[2]%Mod)%Mod,
(a[0]*b[1]%Mod+a[1]*b[3]%Mod)%Mod,
(a[2]*b[0]%Mod+a[3]*b[2]%Mod)%Mod,
(a[2]*b[1]%Mod+a[3]*b[3]%Mod)%Mod};
}
Mat mpow(const Mat &x, ll k) {
Mat a = x;
Mat b{1,0,
0,1};
while (k > 0)
{
if (k & 1)
b = mul(b,a);
a = mul(a,a);
k >>= 1;
}
return b;
}
ll calc(ll x) {
auto a = mpow(Mat{1,1,1,0}, x);
return mul(a, Mat{2,0,
1,0})[2];
}
void solve(void) {
int N;
cin>>N;
vector<ll> C(N);
vector<string> D(N);
REP(i,N)
{
cin>>C[i]>>D[i];
}
ll cnt = 1LL;
REP(i,N)
{
(cnt *= tenPow(calc(C[i]), D[i])) %= Mod;
}
cout<<cnt<<endl;
}
};