結果
問題 | No.1044 正直者大学 |
ユーザー | vwxyz |
提出日時 | 2022-10-01 01:44:45 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 621 ms / 2,000 ms |
コード長 | 3,279 bytes |
コンパイル時間 | 808 ms |
コンパイル使用メモリ | 11,352 KB |
実行使用メモリ | 19,104 KB |
最終ジャッジ日時 | 2023-08-24 19:28:08 |
合計ジャッジ時間 | 6,957 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
11,344 KB |
testcase_01 | AC | 39 ms
11,248 KB |
testcase_02 | AC | 42 ms
11,328 KB |
testcase_03 | AC | 40 ms
11,200 KB |
testcase_04 | AC | 40 ms
11,168 KB |
testcase_05 | AC | 107 ms
19,084 KB |
testcase_06 | AC | 621 ms
19,104 KB |
testcase_07 | AC | 41 ms
11,260 KB |
testcase_08 | AC | 40 ms
11,152 KB |
testcase_09 | AC | 40 ms
11,252 KB |
testcase_10 | AC | 41 ms
11,256 KB |
testcase_11 | AC | 41 ms
11,184 KB |
testcase_12 | AC | 101 ms
16,456 KB |
testcase_13 | AC | 362 ms
16,860 KB |
testcase_14 | AC | 99 ms
18,216 KB |
testcase_15 | AC | 137 ms
18,312 KB |
testcase_16 | AC | 377 ms
18,156 KB |
testcase_17 | AC | 160 ms
16,240 KB |
testcase_18 | AC | 252 ms
15,532 KB |
testcase_19 | AC | 95 ms
15,272 KB |
testcase_20 | AC | 58 ms
13,912 KB |
testcase_21 | AC | 89 ms
14,440 KB |
testcase_22 | AC | 69 ms
15,408 KB |
testcase_23 | AC | 96 ms
17,900 KB |
testcase_24 | AC | 82 ms
17,120 KB |
testcase_25 | AC | 86 ms
18,640 KB |
testcase_26 | AC | 95 ms
18,784 KB |
testcase_27 | AC | 40 ms
11,256 KB |
testcase_28 | AC | 40 ms
11,192 KB |
testcase_29 | AC | 42 ms
11,196 KB |
ソースコード
from ast import Mod import bisect import copy import decimal import fractions import heapq import itertools import math import random import sys import time from collections import Counter,deque,defaultdict from functools import lru_cache,reduce from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max def _heappush_max(heap,item): heap.append(item) heapq._siftdown_max(heap, 0, len(heap)-1) def _heappushpop_max(heap, item): if heap and item < heap[0]: item, heap[0] = heap[0], item heapq._siftup_max(heap, 0) return item from math import gcd as GCD read=sys.stdin.read readline=sys.stdin.readline readlines=sys.stdin.readlines write=sys.stdout.write class MOD: def __init__(self,p,e=None): self.p=p self.e=e if self.e==None: self.mod=self.p else: self.mod=self.p**self.e def Pow(self,a,n): a%=self.mod if n>=0: return pow(a,n,self.mod) else: assert math.gcd(a,self.mod)==1 x=Extended_Euclid(a,self.mod)[0] return pow(x,-n,self.mod) def Build_Fact(self,N): assert N>=0 self.factorial=[1] if self.e==None: for i in range(1,N+1): self.factorial.append(self.factorial[-1]*i%self.mod) else: self.cnt=[0]*(N+1) for i in range(1,N+1): self.cnt[i]=self.cnt[i-1] ii=i while ii%self.p==0: ii//=self.p self.cnt[i]+=1 self.factorial.append(self.factorial[-1]*ii%self.mod) self.factorial_inve=[None]*(N+1) self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1) for i in range(N-1,-1,-1): ii=i+1 while ii%self.p==0: ii//=self.p self.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.mod def Fact(self,N): if N<0: return 0 retu=self.factorial[N] if self.e!=None and self.cnt[N]: retu*=pow(self.p,self.cnt[N],self.mod)%self.mod retu%=self.mod return retu def Fact_Inve(self,N): if self.e!=None and self.cnt[N]: return None return self.factorial_inve[N] def Comb(self,N,K,divisible_count=False): if K<0 or K>N: return 0 retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.mod if self.e!=None: cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K] if divisible_count: return retu,cnt else: retu*=pow(self.p,cnt,self.mod) retu%=self.mod return retu def Extended_Euclid(n,m): stack=[] while m: stack.append((n,m)) n,m=m,n%m if n>=0: x,y=1,0 else: x,y=-1,0 for i in range(len(stack)-1,-1,-1): n,m=stack[i] x,y=y,x-(n//m)*y return x,y N,M,K=map(int,readline().split()) mod=10**9+7 MD=MOD(mod) MD.Build_Fact(max(N,M)) ans=0 for n in range(1,min(N,M)+1): if N+M-2*n>=K: ans+=MD.Comb(N-1,n-1)*MD.Comb(M-1,n-1)%mod*MD.Fact(N)%mod*MD.Fact(M)%mod*MD.Pow(n,-1)%mod ans%=mod print(ans)