M-SOLUTIONS プロコンオープン:E - Product of Arithmetic Progression
問題
解法
公差 d が 0 のとき,求める答えは x * x * ... * x となるので x^n.
そうでないときについて考える.まず,各項を d で割る.そうすると,t = x * mod_inverse(d) とおくと,
t, t + 1, t + 2, ... , t + n - 1
と初項が t で公差が 1 の等差数列を作ることができる.公差が 1 であるのでこれは連続した n 個の整数の積の形になっているので,
(t + n - 1)! / (t - 1)!
と言い換えることができる.前計算で階乗とその逆元を求めておくことで O(1) でこれを計算することができる.ここで,n が n >= 10^9 と大きく,n が大きいケースで TLE となってしまう.よく考えると,n >= mod (= 1000003) のとき,求める数列の要素には必ず mod の倍数が含まれている.よって,n >= mod のときは答えは 0 となり,n < mod のケースのみ先ほどの階乗を用いた計算を行えばよい.前計算がボトルネックとなり O(mod).
解答