結果
問題 | No.1627 三角形の成立 |
ユーザー |
![]() |
提出日時 | 2024-09-26 21:32:07 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 207 ms / 1,000 ms |
コード長 | 712 bytes |
コンパイル時間 | 236 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 93,416 KB |
最終ジャッジ日時 | 2024-09-26 21:32:13 |
合計ジャッジ時間 | 4,893 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 22 |
ソースコード
h,w=map(int,input().split()) n=max(h,w) m=min(h,w) M=10**9+7 L=2*10**5 fa=[1,1] fb=[1,1] for i in range(2,L+1): fa+=[fa[-1]*i%M] fb+=[fb[-1]*(M//i)*fb[M%i]*fa[M%i-1]*(-1)%M] c=lambda n,k:fa[n]*fb[k]*fb[n-k]%M if n>=k else 0 q=[0]*m f=lambda l,i:c((l//i)+1,2)*((l%i)+1)+c((l//i)-1+1,2)*(i-(l%i)-1) for i in range(1,m): g=1 g*=f(h-1,i) g*=f(w-1,i) q[i]=g P=[1]*(L+1) for i in range(2,L+1): if P[i]: for j in range(i+i,L+1,i): P[j]=0 P=[i for i in range(2,L+1) if P[i]] for p in P: for i in range(1,m): if i*p<m: q[i]-=q[i*p] q[i]%=M else: break ans=(h*w)*(h*w-1)*(h*w-2)*fb[3]%M ans-=c(w,3)*h+c(h,3)*w ans-=sum(q[i]*(i-1) for i in range(1,m))*2 ans%=M print(ans)