Submission #00162

ソースコード

?
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
#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a,long long b){
return b ? gcd(b,a%b) : a;
}
long long lcm(long long a,long long b){
return a / gcd(a,b) * b;
}
long long mul(long long a,long long b,const long long mod){
return b?(mul(a*2,b/2,mod)+(b&1?a:0))%mod:0;
}
long long bpow(long long a,long long b,const long long mod){
return (b?bpow(a*a%mod,b/2,mod)*(b&1?a:1):1)%mod;
}
long long repeat(long long a,long long b,const long long mod){
if( b == 0 ) return 0;
long long t = repeat(a,b/2,mod);
long long res = (t * bpow(10,b/2,mod) % mod + t) % mod;
if(b%2){
res = res * 10 + a;
res %= mod;
}
return res;
}
long long inv(long long a,const long long mod){
return bpow(a,mod-2,mod);
}
// to overflow
/*long long bpow(long long a,long long b,const long long mod){
return (b?mul(bpow(mul(a,a,mod),b/2,mod),(b&1?a:1),mod):1)%mod;
}*/
class mInt{
public:
static const long long mod = 1000000007;
long long v;
mInt():v(0){}
mInt(long long v):v((v%mod+mod)%mod){}
};
mInt& operator += (mInt &a,mInt b){ return a = a.v + b.v; }
mInt& operator -= (mInt &a,mInt b){ return a = a.v - b.v; }
mInt& operator *= (mInt &a,mInt b){ return a = a.v * b.v; }
mInt& operator /= (mInt &a,mInt b){ return a = a.v * inv(b.v,mInt::mod); }
mInt operator + (mInt a,mInt b){ return a += b; }
mInt operator - (mInt a,mInt b){ return a -= b; }
mInt operator * (mInt a,mInt b){ return a *= b; }
mInt operator / (mInt a,mInt b){ return a /= b; }
ostream& operator<<(ostream& os, const mInt& x){ return os << x.v; }
template <int N,long long mod>
struct nCr{
vector<long long> f,finv;
long long ncr(long long n,long long r){
if( r > n || r < 0 ) return 0;
assert(n <= N);
return f[n] * finv[r] % mod * finv[n-r] % mod;
}
nCr(){
f.resize(N+1);
finv.resize(N+1);
f[0] = 1;
for(int i = 1 ; i <= N ; i++) f[i] = i * f[i-1] % mod;
finv[N] = inv(f[N],mod);
for(int i = N-1 ; i >= 0 ; i--) finv[i] = finv[i+1] * (i+1)%mod;
}
};
int main(){
nCr<100010,1000000007> ncr;
map<int,long > dcnt;
map<int,long > cnt;
map< pair<int,int> , long long> items;
int N;
cin >> N;
bool positive = 0;
long long sum = 0;
for(int i = 0 ; i < N ; i++){
int A,B;
cin >> A >> B;
items[{A,B}]++;
dcnt[A] += B;
cnt[A] += 1;
positive |= A > 0;
sum += B;
}
if(!positive){ // 0 case
assert( sum == 1 );
cout << 0 << endl;
cout << 1 << endl;
return 0;
}
if( dcnt[0] != 0 ){
mInt ans = 1;
mInt val = 0;
for( auto i : items ){
if( i.first.first != 0 ){
ans *= i.second;
dcnt[i.first.first] -=i.first.second;
cnt[i.first.first]--;
val *= bpow(10,i.first.second,mInt::mod);
val += repeat(i.first.first,i.first.second,mInt::mod);
break;
}
}
for(int i = 0 ; i < 10 ; i++){
val *= bpow(10,dcnt[i],mInt::mod);
val += repeat(i,dcnt[i],mInt::mod);
ans *= ncr.f[cnt[i]];
}
cout << val << endl;
cout << ans << endl;
}else{
mInt val = 0;
mInt ans = 1;
for(int i = 0 ; i < 10 ; i++){
val *= bpow(10,dcnt[i],mInt::mod);
val += repeat(i,dcnt[i],mInt::mod);
ans *= ncr.f[cnt[i]];
}
cout << val << endl;
cout << ans << endl;
}
}

ステータス

項目 データ
問題 0003 - repdigit
ユーザー名 kyuridenamida
投稿日時 2017-07-07 21:33:55
言語 C++11
状態 Accepted
得点 100
ソースコード長 3291 Byte
最大実行時間 97 ms
最大メモリ使用量 8548 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample1.in AC 16 ms 2016 KB
1
01_sample2.in AC 17 ms 1952 KB
1
01_sample3.in AC 13 ms 2016 KB
1
02_handmake1.in AC 13 ms 2088 KB
1
02_handmake2.in AC 18 ms 2152 KB
1
02_handmake3.in AC 17 ms 2216 KB
1
02_handmake4.in AC 15 ms 2152 KB
1
02_handmake5.in AC 20 ms 2216 KB
1
02_handmake6.in AC 18 ms 2160 KB
1
02_handmake7.in AC 15 ms 2228 KB
1
02_handmake8.in AC 11 ms 2164 KB
1
02_handmake9.in AC 13 ms 2104 KB
1
03_random1.in AC 12 ms 2168 KB
1
03_random2.in AC 15 ms 2232 KB
1
03_random3.in AC 22 ms 2168 KB
1
03_random4.in AC 14 ms 2112 KB
1
03_random5.in AC 11 ms 2176 KB
1
03_random6.in AC 18 ms 2120 KB
1
04_random1.in AC 14 ms 2188 KB
1
04_random2.in AC 13 ms 2248 KB
1
04_random3.in AC 14 ms 2184 KB
1
04_random4.in AC 15 ms 2244 KB
1
04_random5.in AC 11 ms 2052 KB
1
04_random6.in AC 13 ms 2116 KB
1
05_random1.in AC 95 ms 8444 KB
1
05_random2.in AC 97 ms 8408 KB
1
05_random3.in AC 90 ms 8368 KB
1
05_random4.in AC 92 ms 8460 KB
1
06_random1.in AC 96 ms 8548 KB
1
06_random3.in AC 96 ms 8384 KB
1