Submission #00106

ソースコード

?
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
#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^(int 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;
res1 = res1 * ten + (ten - 1) / 9 * Mod(i);
}
}
cout << int(res1) << endl;
cout << int(res2) << endl;
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample1.in AC 10 ms 476 KB
1
01_sample2.in AC 11 ms 700 KB
1
01_sample3.in AC 13 ms 664 KB
1
02_handmake1.in AC 18 ms 636 KB
1
02_handmake2.in WA 15 ms 604 KB
1
02_handmake3.in AC 12 ms 564 KB
1
02_handmake4.in AC 12 ms 656 KB
1
02_handmake5.in AC 12 ms 620 KB
1
02_handmake6.in AC 18 ms 584 KB
1
02_handmake7.in AC 13 ms 548 KB
1
02_handmake8.in AC 12 ms 640 KB
1
02_handmake9.in AC 14 ms 480 KB
1
03_random1.in WA 12 ms 580 KB
1
03_random2.in WA 14 ms 540 KB
1
03_random3.in WA 13 ms 636 KB
1
03_random4.in AC 13 ms 596 KB
1
03_random5.in AC 13 ms 684 KB
1
03_random6.in AC 16 ms 644 KB
1
04_random1.in AC 12 ms 476 KB
1
04_random2.in AC 14 ms 564 KB
1
04_random3.in AC 11 ms 524 KB
1
04_random4.in AC 12 ms 484 KB
1
04_random5.in AC 15 ms 580 KB
1
04_random6.in AC 17 ms 420 KB
1
05_random1.in WA 66 ms 1784 KB
1
05_random2.in WA 62 ms 1860 KB
1
05_random3.in WA 63 ms 1808 KB
1
05_random4.in WA 65 ms 1752 KB
1
06_random1.in WA 80 ms 2204 KB
1
06_random3.in WA 68 ms 1744 KB
1