結果
問題 | No.1035 Color Box |
ユーザー | buey_t |
提出日時 | 2023-04-24 11:51:25 |
言語 | PyPy3 (7.3.13) |
結果 |
AC
|
実行時間 | 632 ms / 2,000 ms |
コード長 | 2,466 bytes |
コンパイル時間 | 469 ms |
コンパイル使用メモリ | 87,012 KB |
実行使用メモリ | 257,340 KB |
最終ジャッジ日時 | 2023-08-08 08:14:11 |
合計ジャッジ時間 | 22,290 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 632 ms
256,904 KB |
testcase_01 | AC | 509 ms
257,228 KB |
testcase_02 | AC | 517 ms
257,060 KB |
testcase_03 | AC | 514 ms
257,028 KB |
testcase_04 | AC | 507 ms
256,860 KB |
testcase_05 | AC | 491 ms
257,028 KB |
testcase_06 | AC | 486 ms
257,212 KB |
testcase_07 | AC | 463 ms
257,092 KB |
testcase_08 | AC | 524 ms
257,100 KB |
testcase_09 | AC | 492 ms
257,040 KB |
testcase_10 | AC | 476 ms
256,936 KB |
testcase_11 | AC | 477 ms
256,904 KB |
testcase_12 | AC | 467 ms
257,204 KB |
testcase_13 | AC | 518 ms
257,268 KB |
testcase_14 | AC | 527 ms
257,040 KB |
testcase_15 | AC | 541 ms
257,276 KB |
testcase_16 | AC | 465 ms
257,224 KB |
testcase_17 | AC | 480 ms
257,080 KB |
testcase_18 | AC | 485 ms
257,332 KB |
testcase_19 | AC | 555 ms
256,824 KB |
testcase_20 | AC | 482 ms
256,992 KB |
testcase_21 | AC | 484 ms
256,976 KB |
testcase_22 | AC | 479 ms
257,092 KB |
testcase_23 | AC | 481 ms
257,208 KB |
testcase_24 | AC | 476 ms
256,904 KB |
testcase_25 | AC | 475 ms
257,340 KB |
testcase_26 | AC | 475 ms
256,924 KB |
testcase_27 | AC | 471 ms
257,112 KB |
testcase_28 | AC | 478 ms
256,888 KB |
testcase_29 | AC | 476 ms
257,256 KB |
testcase_30 | AC | 470 ms
257,076 KB |
testcase_31 | AC | 466 ms
257,040 KB |
testcase_32 | AC | 461 ms
257,068 KB |
testcase_33 | AC | 468 ms
257,068 KB |
testcase_34 | AC | 455 ms
257,100 KB |
testcase_35 | AC | 464 ms
256,992 KB |
testcase_36 | AC | 461 ms
256,900 KB |
testcase_37 | AC | 462 ms
257,080 KB |
ソースコード
from math import sqrt,sin,cos,tan,ceil,radians,floor,gcd,exp,log,log10,log2,factorial,fsum from heapq import heapify, heappop, heappush from bisect import bisect_left, bisect_right from copy import deepcopy import copy import random from collections import deque,Counter,defaultdict from itertools import permutations,combinations from decimal import Decimal,ROUND_HALF_UP #tmp = Decimal(mid).quantize(Decimal('0'), rounding=ROUND_HALF_UP) from functools import lru_cache, reduce #@lru_cache(maxsize=None) from operator import add,sub,mul,xor,and_,or_,itemgetter import sys input = sys.stdin.readline # .rstrip() INF = 10**18 mod1 = 10**9+7 mod2 = 998244353 #DecimalならPython #再帰ならPython!!!!!!!!!!!!!!!!!!!!!!!!!! #p = のところを変更すること。 #limitationも必要なら変更 def nCr(n, r, p): if (r < 0) or (n < r): return 0 r = min(r, n - r) return fact[n] * factinv[r] * factinv[n-r] % p p = mod1 limitation = 10 ** 6 # N は必要分だけ用意する fact = [1, 1] # fact[n] = (n! mod p) factinv = [1, 1] # factinv[n] = ((n!)^(-1) mod p) inv = [0, 1] # factinv 計算用 for i in range(2, limitation + 1): fact.append((fact[-1] * i) % p) inv.append((-inv[p % i] * (p // i)) % p) factinv.append((factinv[-1] * inv[-1]) % p) ''' 重複組み合わせっぽいかな まずMをN個にわけてみようか NをM個にわけるのか まあ被り出るな M種類に分ける*M色の組み合わせ M種類に分けるときに、ないやつがあるといけない nCmで、使うやつ決める 次に、pow(m,n-m)か 重複組み合わせで、色の組み合わせは出せる それの並べ方は、適宜出さないといけない M^Nから、一個も配らないやつがある場合を引けばいい つまり、-(M-1)^N * mC1 ここで、余分に引いてしまっている この中にも2個配らない場合は入っていて、それぞれ1個余分である。 なぜなら、1を空にする場合に2が空になっている場合、2を空にする場合に1が空になって言う場合のように 二通りずつ引いてしまっている 次に、これを足す これを繰り返す 箱じゃなくて色を空にする ''' N,M = map(int, input().split()) ans = 0 for i in range(M+1): if i%2 == 0: ans += nCr(M,i,mod1)*pow(M-i,N,mod1)%mod1 else: ans -= nCr(M,i,mod1)*pow(M-i,N,mod1)%mod1 ans %= mod1 print(ans)