結果

問題 No.1025 Modular Equation
ユーザー chocorusk
提出日時 2020-03-05 00:23:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,643 ms / 5,000 ms
コード長 889 bytes
コンパイル時間 161 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 79,060 KB
最終ジャッジ日時 2024-11-30 23:49:00
合計ジャッジ時間 24,294 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math
p, n, k, b=map(int, input().split())
a=list(map(int, input().split()))
r=1
for i in range(1, p):
  dame=False
  pp=1
  for j in range(p-2):
    pp*=i
    pp%=p
    if pp==1:
      dame=True
      break
  if not dame:
    r=i
    break
q=[1]*(p-1)
qi=[0]*p
k=math.gcd(k, p-1)
for i in range(1, p-1):
  q[i]=q[i-1]*r%p
for i in range(p-1):
  qi[q[i]]=i%k
dp=[0]*(k+1)
dp[k]=1
tmp=[0]*(k+1)
MOD=10**9+7
for x in a:
  for j in range(k+1):
    tmp[j]=dp[j]
  for j in range(k):
    for l in range((p-1)//k):
      m=(q[l*k]*x+q[j])%p
      if m==0:
        tmp[k]+=dp[j]*k
        tmp[k]%=MOD
      else:
        tmp[qi[m]]+=dp[j]*k
        tmp[qi[m]]%=MOD
  if x==0:
    tmp[k]+=dp[k]*(p-1)
    tmp[k]%=MOD
  else:
    tmp[qi[x]]+=dp[k]*(p-1)
    tmp[qi[x]]%=MOD
  for j in range(k+1):
    dp[j]=tmp[j]
if b==0:
  print(dp[k])
else:
  print(dp[qi[b]]*pow((p-1)//k, MOD-2, MOD)%MOD)
0