結果

問題 No.1259 スイッチ
ユーザー SPD_9X2
提出日時 2020-10-16 22:26:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 59 ms / 2,000 ms
コード長 763 bytes
コンパイル時間 263 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 58,240 KB
最終ジャッジ日時 2024-07-20 22:30:22
合計ジャッジ時間 4,870 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

https://yukicoder.me/problems/no/1259

M=1以外はすべて同じと扱える
K回後に1にいる場合だけを計算すればよい

1ループがKの約数ならおk
Kの約数でN以下のやつを見つける

"""

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

N,K,M = map(int,input().split())

mans = 0
nfac = 1
mod = 10**9+7

npow = pow(N,N-1,mod)
inv = inverse(N,mod)

for i in range(1,N+1):
    #i回移動で戻る場合を計算する

    if K % i == 0:
        mans += npow * nfac
        mans %= mod

        #print (i,nfac,npow)

    nfac = nfac * (N-i) % mod
    npow = npow * inv % mod

if M == 1:
    print (mans)
else:
    ans = (pow(N,N,mod) - mans) * inverse(N-1,mod) % mod
    print (ans)
0