Submission #00255

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#define INF 1120000000
#define long long long // for codeforces
#define MOD 1000000007
typedef vector<vector<long>> mat;
// return A*B
mat mat_mul(const mat &A, const mat &B){
int n=A.size(), m=B[0].size(), l=B.size();
mat ret(n, vector<long>(m, 0));
rep(i,n) rep(k,l) if(A[i][k]!=0) rep(j,m){
(ret[i][j] += A[i][k] * B[k][j]) %= MOD;
}
return ret;
}
// A^p
mat mat_pow(const mat &A, long p){
int n = A.size();
mat tmp(A), ret(n, vector<long>(n,0));
rep(i,n) ret[i][i] = 1;
while(p>0){
if(p&1) ret = mat_mul(tmp, ret);
tmp = mat_mul(tmp, tmp);
p /= 2;
}
return ret;
}
long fact[100005];
// prevの横にp.fiをp.se個連続
long comp(pair<int,long> p, long prev = 0){
if(prev>=MOD) prev %= MOD;
mat m = {{10,1},{0,1}};
m = mat_pow(m, p.se);
return (m[0][0]*prev + m[0][1]*p.fi)%MOD;
}
int main(){
int n;
cin>>n;
vector<pair<int,int>> vec(n);
rep(i,n) scanf("%d %d", &vec[i].fi, &vec[i].se);
if(n==1){
cout << comp(vec[0]) << endl;
cout << 1 << endl;
return 0;
}
fact[0] = 1;
rep(i,n+3) fact[i+1] = (i+1)*fact[i] % MOD;
bool zero = false;
rep(i,n) if(vec[i].fi==0) zero = true;
long crnt = 0;
int use = -1;
if(zero){
pair<int,int> mn = mp(10,1234567890);
rep(i,n) if(vec[i].fi!=0){
if(vec[i].se < mn.se){
mn = vec[i];
use = i;
}
else if(vec[i].se==mn.se){
if(vec[i].fi < mn.fi){
mn = vec[i];
use = i;
}
}
}
crnt = comp(mn);
}
vector<long> v(10,0);
vector<int> c(10,0);
rep(i,n) if(i!=use){
v[vec[i].fi] += (long)vec[i].se;
c[vec[i].fi]++;
}
long comb = 1;
rep(i,10) if(v[i]>0){
crnt = comp(mp(i, v[i]), crnt);
comb *= fact[c[i]];
comb %= MOD;
}
cout << crnt << endl;
cout << comb << endl;
return 0;
}

ステータス

項目 データ
問題 0003 - repdigit
ユーザー名 tossy
投稿日時 2017-07-07 22:12:33
言語 C++17
状態 Wrong Answer
得点 0
ソースコード長 2729 Byte
最大実行時間 28 ms
最大メモリ使用量 2376 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample1.in AC 13 ms 480 KB
1
01_sample2.in AC 13 ms 588 KB
1
01_sample3.in AC 14 ms 560 KB
1
02_handmake1.in AC 15 ms 404 KB
1
02_handmake2.in WA 15 ms 380 KB
1
02_handmake3.in AC 14 ms 488 KB
1
02_handmake4.in AC 16 ms 592 KB
1
02_handmake5.in AC 13 ms 440 KB
1
02_handmake6.in AC 10 ms 672 KB
1
02_handmake7.in AC 10 ms 644 KB
1
02_handmake8.in AC 14 ms 496 KB
1
02_handmake9.in AC 12 ms 600 KB
1
03_random1.in WA 27 ms 572 KB
1
03_random2.in WA 16 ms 544 KB
1
03_random3.in WA 13 ms 644 KB
1
03_random4.in AC 12 ms 616 KB
1
03_random5.in AC 13 ms 712 KB
1
03_random6.in AC 16 ms 552 KB
1
04_random1.in WA 15 ms 520 KB
1
04_random2.in AC 16 ms 616 KB
1
04_random3.in WA 12 ms 588 KB
1
04_random4.in AC 14 ms 428 KB
1
04_random5.in AC 16 ms 524 KB
1
04_random6.in AC 14 ms 616 KB
1
05_random1.in WA 28 ms 2128 KB
1
05_random2.in WA 25 ms 2332 KB
1
05_random3.in WA 26 ms 2152 KB
1
05_random4.in WA 21 ms 2100 KB
1
06_random1.in AC 21 ms 2176 KB
1
06_random3.in AC 22 ms 2376 KB
1