Submission #00241

ソースコード

?
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
140
141
142
#include <string>
#include <vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<functional>
#include<list>
#include<deque>
#include<bitset>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<cstring>
#include<sstream>
#include<complex>
#include<iomanip>
#include<numeric>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define eb emplace_back
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T> using vv=vector<vector<T>>;
template<class T> ostream& operator<<(ostream &os, const vector<T> &t) {
os<<"{"; rep(i,t.size()) {os<<t[i]<<",";} os<<"}"<<endl; return os;}
template<class S, class T> ostream& operator<<(ostream &os, const pair<S,T> &t) { return os<<"("<<t.first<<","<<t.second<<")";}
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}
#define out(args...){vector<string> a_r_g_s=s_p_l_i_t(#args, ','); e_r_r(a_r_g_s.begin(), args); }
vector<string> s_p_l_i_t(const string &s, char c){vector<string> v;int d=0,f=0;string t;for(char c:s){if(!d&&c==',')v.pb(t),t="";else t+=c;if(c=='\"'||c=='\'')f^=1;if(!f&&c=='(')++d;if(!f&&c==')')--d;}v.pb(t);return move(v);}
void e_r_r(vector<string>::iterator it) {}
template<typename T, typename... Args> void e_r_r(vector<string>::iterator it, T a, Args... args){ if(*it==" 1"||*it=="1") cerr<<endl; else cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; e_r_r(++it, args...);}
const ll MOD=1e9+7;
ll modpow(ll r,ll n,ll m=MOD){
ll re=1,d=r%m;
if(n<0)(n%=m-1)+=m-1;
for(;n;n/=2){
if(n&1)(re*=d)%=m;
(d*=d)%=m;
}
return re;
}
template <int mod=MOD> struct modInt{
int v;
modInt(int v=0):v(v){}
modInt operator+(const modInt &n){return v+n.v<mod ? v+n.v : v+n.v-mod;}
modInt operator-(const modInt &n){return v-n.v<0 ? v-n.v+mod : v-n.v;}
modInt operator*(const modInt &n){return ll(v)*n.v%mod;}
modInt operator/(const modInt &n){return ll(v)*modpow(n.v%mod,-1,mod)%mod;}
template<class T> modInt operator+(const T &n){return v+n<mod ? v+n : v+n-mod;}
template<class T> modInt operator-(const T &n){return v-n<0 ? v-n+mod : v-n;}
template<class T> modInt operator*(const T &n){return ll(v)*(n%mod)%mod;}
template<class T> modInt operator/(const T &n){return ll(v)*modpow(n%mod,-1,mod)%mod;}
modInt& operator+=(const modInt &n){v+=n.v; if(v>=mod) v-=mod; return *this;}
modInt& operator-=(const modInt &n){v-=n.v; if(v<0) v+=mod; return *this;}
modInt& operator*=(const modInt &n){v=ll(v)*n.v%mod; return *this;}
modInt& operator/=(const modInt &n){v=ll(v)*modpow(n.v,-1,mod)%mod; return *this;}
template<class T> modInt& operator+=(const T &n){v+=n; if(v>=mod) v-=mod; return *this;}
template<class T> modInt& operator-=(const T &n){v-=n; if(v<0) v+=mod; return *this;}
template<class T> modInt& operator*=(const T &n){v=ll(v)*n%mod; return *this;}
template<class T> modInt& operator/=(const T &n){v=ll(v)*modpow(n,-1,mod)%mod; return *this;}
};
template<int mod> ostream& operator<<(ostream &os,const modInt<mod> &n){return os<<n.v;};
template<class T,int mod> modInt<mod> operator+(const T &n,const modInt<mod> &m){return m.v+n<mod ? m.v+n : m.v+n-mod;}
template<class T,int mod> modInt<mod> operator-(const T &n,const modInt<mod> &m){return n-m.v<0 ? n-m.v+mod : n-m.v;}
template<class T,int mod> modInt<mod> operator*(const T &n,const modInt<mod> &m){return ll(m.v)*(n%mod)%mod;}
template<class T,int mod> modInt<mod> operator/(const T &n,const modInt<mod> &m){return ll(m.v)*modpow(n%mod,-1,mod)%mod;}
typedef modInt<MOD> mint;
template <int mod> modInt<mod> modpow(modInt<mod> r,ll n){ modInt<mod> re(1); if(n<0)(n%=mod-1)+=mod-1; for(;n;n/=2){if(n&1) re*=r; r*=r;} return re;}
vector<mint> fact,finv,inv;
mint comb(ll n,ll r){ if(n<r||r<0)return 0; return fact[n]*finv[n-r]*finv[r];}
class Doralion{
void Modinvs(vector<mint> &re,int n){ re.resize(n+1); re[1]=1; for(int i=2;i<=n;++i)re[i]=re[MOD%i]*(MOD-MOD/i);}
void Facts(vector<mint> &re,int n){ re.resize(n+1); re[0]=1; rep(i,n)re[i+1]=re[i]*(i+1);}
void Factinvs(vector<mint> &re,const vector<mint> &inv,int n){ re.resize(n+1); re[0]=1; rep(i,n)re[i+1]=re[i]*inv[i+1];}
public:
Doralion(int n){ Modinvs(inv,n); Facts(fact,n); Factinvs(finv,inv,n);}
} doralion(212345);
mint fun(ll d){
return inv[9]*(modpow(10,d)-1);
}
int main(){
ios_base::sync_with_stdio(false);
cout<<fixed<<setprecision(0);
int n;
cin>>n;
vector<pll> ps;
ll zero=0;
vector<int> cnt(10);
rep(i,n){
ll x,y;
cin>>x>>y;
if(x) ps.eb(x,y);
else zero+=y;
++cnt[x];
}
if(ps.size()==0){
cout<<"0\n1\n";
return 0;
}
sort(all(ps));
mint re=0,ret=1;
if(zero){
sort(all(ps),[&](pll p,pll q){return pll(p.Y,p.X)<pll(q.Y,q.X);});
int t=0;
rep(i,ps.size()) if(ps[i]==ps[0]) ++t;
ret*=t;
--cnt[ps[0].X];
(re*=modpow(10,ps[0].Y))+=ps[0].X*fun(ps[0].Y);
ps.erase(ps.begin());
}
sort(all(ps));
// out(ps,1);
re*=modpow(10,zero);
for(pll p:ps) (re*=modpow(10,p.Y))+=p.X*fun(p.Y);
rep(i,10) ret*=fact[cnt[i]];
cout<<re<<"\n"<<ret<<endl;
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample1.in AC 21 ms 2912 KB
1
01_sample2.in AC 21 ms 2940 KB
1
01_sample3.in AC 20 ms 3088 KB
1
02_handmake1.in AC 21 ms 3112 KB
1
02_handmake2.in AC 20 ms 3136 KB
1
02_handmake3.in AC 21 ms 3028 KB
1
02_handmake4.in AC 23 ms 3048 KB
1
02_handmake5.in AC 18 ms 2936 KB
1
02_handmake6.in AC 18 ms 2956 KB
1
02_handmake7.in AC 22 ms 2980 KB
1
02_handmake8.in AC 16 ms 3004 KB
1
02_handmake9.in AC 17 ms 3024 KB
1
03_random1.in AC 17 ms 3048 KB
1
03_random2.in AC 17 ms 3196 KB
1
03_random3.in AC 17 ms 3216 KB
1
03_random4.in AC 16 ms 3232 KB
1
03_random5.in AC 20 ms 3244 KB
1
03_random6.in AC 20 ms 3260 KB
1
04_random1.in WA 18 ms 3152 KB
1
04_random2.in AC 17 ms 3304 KB
1
04_random3.in WA 16 ms 3192 KB
1
04_random4.in AC 21 ms 3212 KB
1
04_random5.in AC 20 ms 3104 KB
1
04_random6.in AC 21 ms 3124 KB
1
05_random1.in WA 70 ms 5312 KB
1
05_random2.in WA 72 ms 5316 KB
1
05_random3.in WA 78 ms 5320 KB
1
05_random4.in WA 71 ms 5324 KB
1
06_random1.in AC 31 ms 3164 KB
1
06_random3.in AC 69 ms 5348 KB
1