Submission #00262

ソースコード

?
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
143
#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);});
// 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:15:30
言語 C++17
状態 Accepted
得点 100
ソースコード長 5977 Byte
最大実行時間 67 ms
最大メモリ使用量 5300 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample1.in AC 28 ms 2912 KB
1
01_sample2.in AC 18 ms 2932 KB
1
01_sample3.in AC 18 ms 2956 KB
1
02_handmake1.in AC 19 ms 2844 KB
1
02_handmake2.in AC 20 ms 2868 KB
1
02_handmake3.in AC 18 ms 2888 KB
1
02_handmake4.in AC 36 ms 2912 KB
1
02_handmake5.in AC 19 ms 2928 KB
1
02_handmake6.in AC 17 ms 2952 KB
1
02_handmake7.in AC 19 ms 2972 KB
1
02_handmake8.in AC 18 ms 3000 KB
1
02_handmake9.in AC 20 ms 3024 KB
1
03_random1.in AC 20 ms 2920 KB
1
03_random2.in AC 18 ms 2940 KB
1
03_random3.in AC 20 ms 2956 KB
1
03_random4.in AC 17 ms 2972 KB
1
03_random5.in AC 18 ms 2996 KB
1
03_random6.in AC 18 ms 3008 KB
1
04_random1.in AC 23 ms 3024 KB
1
04_random2.in AC 21 ms 3044 KB
1
04_random3.in AC 18 ms 3060 KB
1
04_random4.in AC 19 ms 3080 KB
1
04_random5.in AC 22 ms 3096 KB
1
04_random6.in AC 19 ms 3112 KB
1
05_random1.in AC 63 ms 5292 KB
1
05_random2.in AC 67 ms 5296 KB
1
05_random3.in AC 58 ms 5300 KB
1
05_random4.in AC 63 ms 5300 KB
1
06_random1.in AC 31 ms 3012 KB
1
06_random3.in AC 57 ms 5200 KB
1