Submission #00163

ソースコード

?
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
template<int M, bool IsPrime = false>
class Modulo {
using ll = long long;
int n;
static enable_if_t<IsPrime, ll> inv(ll a, ll p) {
return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
public:
Modulo () : n(0) {;}
Modulo (int m) : n(m) {
if (n >= M) n %= M;
else if (n < 0) n = (n % M + M) % M;
}
Modulo (ll m) {
if (m >= M) m %= M;
else if (m < 0) m = (m % M + M) % M;
n = m;
}
explicit operator int() const { return n; }
explicit operator ll() const { return n; }
bool operator==(const Modulo &a) const { return n == a.n; }
Modulo operator+=(const Modulo &a) { n += a.n; if (n >= M) n -= M; return *this; }
Modulo operator-=(const Modulo &a) { n -= a.n; if (n < 0) n += M; return *this; }
Modulo operator*=(const Modulo &a) { n = (ll(n) * a.n) % M; return *this; }
Modulo operator+(const Modulo &a) const { Modulo res = *this; return res += a; }
Modulo operator-(const Modulo &a) const { Modulo res = *this; return res -= a; }
Modulo operator*(const Modulo &a) const { Modulo res = *this; return res *= a; }
Modulo operator^(ll n) const {
if (n == 0) return Modulo(1);
const Modulo a = *this;
Modulo res = (a * a) ^ (n / 2);
return n % 2 ? res * a : res;
}
enable_if_t<IsPrime, Modulo> operator/(const Modulo &a) const {
return *this * inv(ll(a), M);
}
};
const int mod = 1000000007;
template<int M = mod> Modulo<M, true> fact(int n, bool sw = true) {
static vector<Modulo<M, true>> v1 = {1}, v2 = {1};
if (n >= (int)v1.size()) {
const int from = v1.size(), to = n + 1024;
v1.reserve(to);
v2.reserve(to);
for (int i = from; i < to; ++i) {
v1.push_back(v1.back() * Modulo<M, true>(i));
v2.push_back(v2.back() / Modulo<M, true>(i));
}
}
return sw ? v1[n] : v2[n];
}
template<int M = mod> Modulo<M, true> comb(int a, int b) {
if (b < 0 || b > a) return 0;
return fact<M>(a, true) * fact<M>(b, false) * fact<M>(a-b, false);
}
using Mod = Modulo<mod, true>;
int main() {
int n;
cin >> n;
vector<pair<int,int>> vec;
REP(i,n) {
int a, b;
cin >> a >> b;
vec.emplace_back(a, b);
}
sort(ALL(vec));
Mod res1 = 0;
Mod res2 = 1;
if (vec.front().first == 0) {
auto it1 = lower_bound(ALL(vec), make_pair(0, 0));
auto it2 = lower_bound(ALL(vec), make_pair(1, 0));
if (it2 == end(vec)) {
cout << int(res1) << endl;
cout << int(res2) << endl;
return 0;
}
res2 = Mod(fact(it2 - it1));
auto p = *it2;
auto it3 = upper_bound(ALL(vec), p);
res2 *= Mod(fact(it3 - it2));
auto it4 = lower_bound(ALL(vec), make_pair(p.first + 1, 0));
res2 *= Mod(fact(it4 - it2 - 1));
res1 = ((Mod(10) ^ p.second) - 1) / Mod(9) * Mod(p.first);
ll sum = 0;
for (auto it = it1; it != it2; ++it) sum += it->second;
Mod ten = Mod(10) ^ sum;
res1 = res1 * ten;
sum = 0;
for (auto it = it2 + 1; it != it4; ++it) sum += it->second;
ten = Mod(10) ^ sum;
res1 = res1 * ten + (ten - 1) / Mod(9) * Mod(it2->first);
sum = 0;
for (int i = p.first + 1; i < 10; ++i) {
auto it1 = lower_bound(ALL(vec), make_pair(i, 0));
auto it2 = lower_bound(ALL(vec), make_pair(i + 1, 0));
res2 *= Mod(fact(it2 - it1));
sum = 0;
for (auto it = it1; it != it2; ++it) sum += it->second;
ten = Mod(10) ^ sum;
res1 = res1 * ten + (ten - 1) / Mod(9) * Mod(it1->first);
}
}
else {
REP(i,10) {
auto it1 = lower_bound(ALL(vec), make_pair(i, 0));
auto it2 = lower_bound(ALL(vec), make_pair(i + 1, 0));
res2 *= Mod(fact(it2 - it1));
ll sum = 0;
for (auto it = it1; it != it2; ++it) sum += it->second;
Mod ten = Mod(10) ^ sum;
// cout << int(ten) << endl;
res1 = res1 * ten + (ten - 1) / 9 * Mod(i);
}
}
cout << int(res1) << endl;
cout << int(res2) << endl;
return 0;
}

ステータス

項目 データ
問題 0003 - repdigit
ユーザー名 鬼勃ち
投稿日時 2017-07-07 21:34:11
言語 C++17
状態 Wrong Answer
得点 0
ソースコード長 4175 Byte
最大実行時間 85 ms
最大メモリ使用量 2220 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample1.in AC 13 ms 480 KB
1
01_sample2.in AC 11 ms 444 KB
1
01_sample3.in AC 14 ms 408 KB
1
02_handmake1.in AC 14 ms 380 KB
1
02_handmake2.in WA 19 ms 344 KB
1
02_handmake3.in AC 17 ms 568 KB
1
02_handmake4.in AC 13 ms 532 KB
1
02_handmake5.in AC 12 ms 504 KB
1
02_handmake6.in AC 14 ms 472 KB
1
02_handmake7.in AC 11 ms 436 KB
1
02_handmake8.in AC 15 ms 524 KB
1
02_handmake9.in AC 12 ms 496 KB
1
03_random1.in WA 12 ms 588 KB
1
03_random2.in WA 16 ms 424 KB
1
03_random3.in WA 13 ms 516 KB
1
03_random4.in AC 12 ms 608 KB
1
03_random5.in AC 15 ms 696 KB
1
03_random6.in AC 12 ms 660 KB
1
04_random1.in AC 13 ms 620 KB
1
04_random2.in AC 12 ms 584 KB
1
04_random3.in AC 13 ms 548 KB
1
04_random4.in AC 11 ms 508 KB
1
04_random5.in AC 20 ms 596 KB
1
04_random6.in AC 12 ms 560 KB
1
05_random1.in AC 65 ms 1668 KB
1
05_random2.in AC 61 ms 1740 KB
1
05_random3.in AC 59 ms 1688 KB
1
05_random4.in AC 62 ms 1764 KB
1
06_random1.in AC 85 ms 2220 KB
1
06_random3.in AC 59 ms 1760 KB
1