Submission #21080

ソースコード

?
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
89
90
91
92
93
94
95
96
97
98
99
100
101
// 基本テンプレート
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
typedef pair<int, int> pii;
typedef long long ll;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;
int N, fact[100010];
pii arms[100010];
ll mod_pow(ll x, ll n) {return (!n)?1:(mod_pow((x*x)%MOD,n/2)*((n&1)?x:1))%MOD;}
// A が B こ並んだ数
ll calc(int A, int B) {
ll x = (mod_pow(10, B) - 1 + MOD) % MOD;
(x *= A) %= MOD;
return (x * mod_pow(9, MOD-2)) % MOD;
}
signed main() {
fact[0] = 1;
rep(i,1,100010) fact[i] = fact[i-1] * i;
cin >> N;
rep(i,0,N) {
int A, B; cin >> A >> B;
arms[i] = pii(A, B);
}
sort(arms, arms + N);
int cntzero = upper_bound(arms, arms+N, pii(0, INF)) - arms;
int sum = 0;
rep(i,0,cntzero) sum += arms[i].second;
int num = 0, ans = fact[cntzero], prev = arms[cntzero].first, cnt = 0, top = 0;
if(cntzero == N) {
cout << num << endl << ans << endl;
return 0;
}
rep(i,cntzero,N) {
// printf("num = %lld, ans = %lld, prev = %lld, cnt = %lld\n", num, ans, prev, cnt);
ll pw = mod_pow(10, arms[i].second);
(num *= pw) %= MOD;
(num += calc(arms[i].first, arms[i].second)) %= MOD;
if(i == cntzero) {
ll pw = mod_pow(10, sum);
(num *= pw) %= MOD;
}
// 最初の要素とおなじやつ
if(arms[cntzero] == arms[i]) top++;
// 前の数字とおなじやつかどうか
if(prev == arms[i].first) cnt++;
else {
if(arms[i-1].first == prev) (ans *= fact[cnt-1]) %= MOD;
else (ans *= fact[cnt]) %= MOD;
cnt = 1; prev = arms[i].first;
}
}
(ans *= fact[cnt]) %= MOD;
(ans *= top) %= MOD;
cout << num << endl << ans << endl;
return 0;
}

ステータス

項目 データ
問題 0758 - repdigit
ユーザー名 tsutaj
投稿日時 2017-07-08 00:25:01
言語 C++11
状態 Wrong Answer
得点 0
ソースコード長 2739 Byte
最大実行時間 118 ms
最大メモリ使用量 3068 KB

セット

セット 得点 Cases
1 ALL 0 / 10 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample1.in AC 14 ms 1248 KB
1
01_sample2.in AC 14 ms 1208 KB
1
01_sample3.in AC 13 ms 1296 KB
1
02_handmake1.in AC 17 ms 1252 KB
1
02_handmake2.in WA 11 ms 1208 KB
1
02_handmake3.in WA 11 ms 1288 KB
1
02_handmake4.in AC 14 ms 1244 KB
1
02_handmake5.in AC 11 ms 1204 KB
1
02_handmake6.in AC 12 ms 1292 KB
1
02_handmake7.in AC 11 ms 1384 KB
1
02_handmake8.in AC 28 ms 1340 KB
1
02_handmake9.in AC 11 ms 1428 KB
1
03_random1.in WA 13 ms 1392 KB
1
03_random2.in WA 11 ms 1348 KB
1
03_random3.in WA 14 ms 1304 KB
1
03_random4.in WA 11 ms 1384 KB
1
03_random5.in WA 14 ms 1464 KB
1
03_random6.in WA 11 ms 1416 KB
1
04_random1.in WA 14 ms 1368 KB
1
04_random2.in WA 14 ms 1448 KB
1
04_random3.in WA 14 ms 1404 KB
1
04_random4.in WA 11 ms 1360 KB
1
04_random5.in WA 10 ms 1308 KB
1
04_random6.in WA 14 ms 1264 KB
1
05_random1.in WA 111 ms 2880 KB
1
05_random2.in WA 107 ms 2944 KB
1
05_random3.in WA 111 ms 3008 KB
1
05_random4.in WA 118 ms 3068 KB
1
06_random1.in WA 60 ms 3004 KB
1
06_random3.in WA 116 ms 2936 KB
1