powering

累乗って,いままで,

inline void pow(int a[N], long long n) {
if (n == 1) {
return;
} else if (n%2) {
int b[N];
REP (i, N) b[i] = a[i];
pow(b, n-1), mul(a, b);
} else {
mul(a, a), pow(a, n/2);
}
}

こんな,ふうに書いていた.

(配列を累乗しているのは大人の事情です.)

しかし,実は,別の書きかたもあった.

// initialize b = 1;
while (n>1) {
if (n%2) mul(b, a);
mul(a,a), n /= 2;
}
mul(a,b);

こっちのほうが,断然短くて,見た目はカッコイイ.

# 可読性は悪いような...

More Reading
Older// sagemath