Submission #995225
Source Code Expand
#include<bits/stdc++.h> using namespace std; typedef long long int64; const int mod = 1e9 + 7; inline int64 modPow(int64 x, int64 n) { if(n == 0) return (1); int64 ret = modPow(x, n / 2); (ret *= ret) %= mod; if(n & 1) (ret *= x) %= mod; return (ret); } inline int64 modInv(int64 a) { return (modPow(a, mod - 2)); } inline int64 modCombination(int p, int q) { static int64 fact[202020], rfact[202020]; if(fact[0] == 0) { fact[0] = rfact[0] = 1; for(int i = 1; i < 102020; i++) { fact[i] = fact[i - 1] * i % mod; rfact[i] = modInv(fact[i]); } } if(q < 0 || p < q) return (0); return (fact[p] * rfact[q] % mod * rfact[p - q] % mod); } inline int64 count1_3(int n, int k) { if(n < k) return (0); int64 ret = 0; for(int i = 1; i <= k; i++) { // i 個以下の箱に n 個の玉を入れる場合の数 int64 tmp = modCombination(k, i) * modPow(i, n) % mod; if((k - i) & 1) ret = (ret - tmp + mod) % mod; else (ret += tmp) %= mod; } return (ret); } inline int64 modFact(int n) { int64 ret = 1; while(n > 1) (ret *= n--) %= mod; return (ret); } inline int64 count2_3(int n, int k) { if(n < k) return (0); return (count1_3(n, k) * modInv(modFact(k)) % mod); } int main() { int N, K; cin >> K >> N; cout << count2_3(N, K) << endl; }
Submission Info
Submission Time | |
---|---|
Task | F - Road of the King |
User | ei13333 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1385 Byte |
Status | WA |
Exec Time | 26 ms |
Memory | 1920 KB |
Judge Result
Set Name | sample | all | ||||||||
---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1000 | ||||||||
Status |
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt, sample-03.txt |
all | sample-01.txt, sample-02.txt, sample-03.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 2 ms | 256 KB |
01-02.txt | AC | 26 ms | 1792 KB |
01-03.txt | WA | 26 ms | 1792 KB |
01-04.txt | AC | 2 ms | 256 KB |
01-05.txt | WA | 26 ms | 1792 KB |
01-06.txt | WA | 26 ms | 1792 KB |
01-07.txt | WA | 26 ms | 1792 KB |
01-08.txt | WA | 26 ms | 1792 KB |
01-09.txt | WA | 26 ms | 1792 KB |
01-10.txt | WA | 26 ms | 1792 KB |
sample-01.txt | WA | 26 ms | 1920 KB |
sample-02.txt | WA | 26 ms | 1792 KB |
sample-03.txt | AC | 2 ms | 256 KB |