結果
問題 |
No.1044 正直者大学
|
ユーザー |
|
提出日時 | 2021-06-16 13:22:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 167 ms / 2,000 ms |
コード長 | 1,062 bytes |
コンパイル時間 | 296 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 119,552 KB |
最終ジャッジ日時 | 2024-12-30 09:23:36 |
合計ジャッジ時間 | 4,021 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 28 |
ソースコード
""" 紹介する方、される方->発表 oo->o xo->x ox->x xx->o 同じ所属の学生が連続していると正直者大学として紹介される。 所属が切り替わる場所がx箇所あるとすると、n+m-x人が正直者大学として紹介される。 xは偶数 n+m-x>=k <=> n+m-k>=x 並べ方全体は(n+m)!/(n+m)=(n+m-1)! 所属が切り替わる場所がx箇所ある並べ方 正直者1人の場所を固定し、その人からの相対位置を考える。 ((n-1)! * cmb(n,x//2) * (m! * cmb(m-1,x//2-1)) """ n,m,k=map(int,input().split()) mod=10**9+7 def cmb(n,r,mod=mod): if (r<0 or r>n): return 0 r=min(r,n-r) return (g1[n]*g2[r]*g2[n-r])%mod g1=[1,1] # g1[i]=i! % mod :階乗 g2=[1,1] # g2[i]=(i!)^(-1) % mod :階乗の逆元 inverse=[0,1] for i in range(2,n+m+1): g1.append((g1[-1]*i)%mod) inverse.append((-inverse[mod%i]*(mod//i))%mod) g2.append((g2[-1]*inverse[-1])%mod) ans=0 for x in range(2,n+m+1,2): if n+m-x<k:break tmp=g1[n-1]*cmb(n,x//2)*g1[m]*cmb(m-1,x//2-1)%mod ans+=tmp ans%=mod print(ans)