Submission #1511195
Source Code Expand
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; const int INF = 1e8; using namespace std; typedef unsigned long long ull; const ull M = 1000000007; //べき乗 x^n mod M ull power(ull x, ull n){ ull res = 1; if(n > 0){ res = power(x, n / 2); if(n % 2 == 0) res = (res * res) % M; else res = (((res * res) % M) * x ) % M; } return res; } //階乗 ull factorial(ull n, ull r){ ull res = 1; range(i,r,n + 1){ res*= i; res%= M; } return res; } //nCr コンビネーション (1,1)から(w,h)だと、引数は(w - 1, h - 1, M) ull combination(ull n, ull r){ //nCr = n! / ( (n - r)! * r! ) ull a = factorial(n, n - r + 1); ull b = factorial(r,1) % M; return a * power(b, M - 2) % M; } ull solve(ull dif, ull num){ //show(dif) show(num) return combination(dif + num, num); } int main(){ ull n; cin >> n; vector<int> v; rep(i,n){ int a; cin >> a; v.emplace_back(a); } ull ans = 1; ull dif = v[0], num = 0; //数字の差、項の数 range(i,1,n){ if(v[i] == -1){ num++; }else{ (ans *= solve(v[i] - dif, num)) %= M; num = 0; dif = v[i]; } } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | C - タコヤ木 |
User | noy72 |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 1530 Byte |
Status | AC |
Exec Time | 2 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | Subtask3 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 50 / 50 | 30 / 30 | 20 / 20 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
Subtask1 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Subtask3 | sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask1_01.txt | AC | 1 ms | 256 KB |
subtask1_02.txt | AC | 1 ms | 256 KB |
subtask1_03.txt | AC | 1 ms | 256 KB |
subtask1_04.txt | AC | 1 ms | 256 KB |
subtask1_05.txt | AC | 1 ms | 256 KB |
subtask1_06.txt | AC | 1 ms | 256 KB |
subtask1_07.txt | AC | 1 ms | 256 KB |
subtask1_08.txt | AC | 1 ms | 256 KB |
subtask1_09.txt | AC | 1 ms | 256 KB |
subtask1_10.txt | AC | 1 ms | 256 KB |
subtask1_11.txt | AC | 1 ms | 256 KB |
subtask1_12.txt | AC | 1 ms | 256 KB |
subtask2_01.txt | AC | 1 ms | 256 KB |
subtask2_02.txt | AC | 1 ms | 256 KB |
subtask2_03.txt | AC | 1 ms | 256 KB |
subtask2_04.txt | AC | 1 ms | 256 KB |
subtask2_05.txt | AC | 2 ms | 256 KB |
subtask2_06.txt | AC | 1 ms | 256 KB |
subtask2_07.txt | AC | 1 ms | 256 KB |
subtask2_08.txt | AC | 2 ms | 256 KB |
subtask2_09.txt | AC | 1 ms | 256 KB |
subtask2_10.txt | AC | 1 ms | 256 KB |
subtask2_11.txt | AC | 2 ms | 256 KB |
subtask2_12.txt | AC | 2 ms | 256 KB |
subtask3_01.txt | AC | 1 ms | 256 KB |
subtask3_02.txt | AC | 1 ms | 256 KB |
subtask3_03.txt | AC | 1 ms | 256 KB |
subtask3_04.txt | AC | 2 ms | 256 KB |
subtask3_05.txt | AC | 1 ms | 256 KB |
subtask3_06.txt | AC | 2 ms | 256 KB |
subtask3_07.txt | AC | 1 ms | 256 KB |
subtask3_08.txt | AC | 2 ms | 256 KB |
subtask3_09.txt | AC | 2 ms | 256 KB |
subtask3_10.txt | AC | 2 ms | 256 KB |
subtask3_11.txt | AC | 2 ms | 256 KB |
subtask3_12.txt | AC | 2 ms | 256 KB |