【今日の精進】M-SOLUTIONS2019E - Product of Arithmetic Progression

毎日格上の問題を倒すやつの86日目です。

問題リンク

atcoder.jp

問題概要

の積を で割ったあまりを求めてね。

解法

か の時は先に処理します。これはどちらも容易です。

の場合は非常に簡単です。階乗を前計算して、 倍すればよいです。

一般の場合でも、逆数でいい感じに計算すれば同じ状況のものが二つになります。なので割り算すればよいです。

提出コード

MOD=1000003
fact=[1]*(MOD+1)
for i in range(1,MOD+1):
    fact[i]=(fact[i-1]*i)%MOD
Q=int(input())
for _ in range(Q):
    x,d,n=map(int,input().split())
    if x==0:
        print(0)
        continue
    if d==0:
        print(pow(x,n,MOD))
        continue
    pos=(x*pow(d,-1,MOD)%MOD)
    if pos+n-1>=MOD:
        print(0)
        continue
    print(pow(d,n,MOD)*fact[pos+n-1]*pow(fact[pos-1],-1,MOD)%MOD)

Submission #48499217 - M-SOLUTIONS Programming Contest

解法

久しぶりにらくちんでした