Submission #00353
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 | //スパゲッティー #include <iostream> #include <algorithm> #define int long long using namespace std; int powmod( int a, int n, int mod) { if (n == 0) return 1; if (n % 2 == 0) return powmod((a * a) % mod, n / 2, mod); return (a * powmod(a, n - 1, mod)) % mod; } int mod = 1000000007; int n; int numCnt[10], minLength[10], minObjCnt[10]; int objCnt[10]; int fact[100001]; signed main() { int i; cin >> n; fact[0] = 1; for (i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % mod; for (i = 0; i < 10; i++) minLength[i] = 1145141919; for (i = 0; i < n; i++) { int a, b; cin >> a >> b; objCnt[a]++; numCnt[a] += b; if (minLength[a] > b) { minLength[a] = b; minObjCnt[a] = 1; } else if (minLength[a] == b) { minObjCnt[a]++; } } for (i = 1; i < 10; i++) { if (objCnt[i] != 0) { break ; } } i %= 10; //数字iを先頭に置く numCnt[i] -= minLength[i]; objCnt[i]--; //最小コスト(シフトして足して引く, あの等比数列の公式を使うとか使わないとか) int x, ans = 0, length = 0; for ( int j = 9; j >= 0; j--) { x = ((powmod(10, numCnt[j], mod) + mod - 1) * powmod(9, mod - 2, mod)) % mod; x = (j * x) % mod; x = (x * powmod(10, length, mod)) % mod; ans = (ans + x) % mod; length += numCnt[j]; } x = ((powmod(10, minLength[i], mod) + mod - 1) * powmod(9, mod - 2, mod)) % mod; x = (i * x) % mod; x = (x * powmod(10, length, mod)) % mod; ans = (ans + x) % mod; //組み合わせの数 int permCnt = 1; int j; for (j = 9; j > i; j--) if (objCnt[j] > 0) break ; if (j == i) { permCnt *= objCnt[i] + 1; permCnt %= mod; } else { permCnt *= minObjCnt[i]; permCnt %= mod; } for (i = 0; i < 10; i++) { permCnt *= fact[objCnt[i]]; permCnt %= mod; } cout << ans << endl; cout << permCnt << endl; return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 0003 - repdigit |
ユーザー名 | startcpp |
投稿日時 | 2017-07-07 22:57:07 |
言語 | C++11 |
状態 | Wrong Answer |
得点 | 0 |
ソースコード長 | 1922 Byte |
最大実行時間 | 55 ms |
最大メモリ使用量 | 1508 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 0 / 100 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
01_sample1.in | AC | 15 ms | 480 KB |
1
|
01_sample2.in | AC | 14 ms | 448 KB |
1
|
01_sample3.in | AC | 17 ms | 548 KB |
1
|
02_handmake1.in | AC | 12 ms | 520 KB |
1
|
02_handmake2.in | AC | 18 ms | 488 KB |
1
|
02_handmake3.in | WA | 54 ms | 456 KB |
1
|
02_handmake4.in | AC | 15 ms | 556 KB |
1
|
02_handmake5.in | AC | 15 ms | 396 KB |
1
|
02_handmake6.in | AC | 13 ms | 368 KB |
1
|
02_handmake7.in | AC | 13 ms | 596 KB |
1
|
02_handmake8.in | AC | 12 ms | 692 KB |
1
|
02_handmake9.in | AC | 14 ms | 532 KB |
1
|
03_random1.in | AC | 12 ms | 500 KB |
1
|
03_random2.in | AC | 14 ms | 464 KB |
1
|
03_random3.in | AC | 16 ms | 436 KB |
1
|
03_random4.in | AC | 11 ms | 664 KB |
1
|
03_random5.in | AC | 12 ms | 760 KB |
1
|
03_random6.in | AC | 14 ms | 600 KB |
1
|
04_random1.in | AC | 11 ms | 568 KB |
1
|
04_random2.in | AC | 10 ms | 540 KB |
1
|
04_random3.in | AC | 11 ms | 508 KB |
1
|
04_random4.in | WA | 12 ms | 480 KB |
1
|
04_random5.in | WA | 11 ms | 576 KB |
1
|
04_random6.in | WA | 14 ms | 548 KB |
1
|
05_random1.in | AC | 51 ms | 1284 KB |
1
|
05_random2.in | AC | 55 ms | 1372 KB |
1
|
05_random3.in | AC | 51 ms | 1328 KB |
1
|
05_random4.in | AC | 51 ms | 1416 KB |
1
|
06_random1.in | AC | 49 ms | 1508 KB |
1
|
06_random3.in | AC | 51 ms | 1472 KB |
1
|