Submission #00237

ソースコード

?
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(int 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"<<endl;
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);
// out(ps[0],1);
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:03:56
言語 C++17
状態 Wrong Answer
得点 0
ソースコード長 5931 Byte
最大実行時間 75 ms
最大メモリ使用量 5352 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
01_sample1.in AC 17 ms 2912 KB
1
01_sample2.in AC 19 ms 2936 KB
1
01_sample3.in WA 23 ms 2960 KB
1
02_handmake1.in AC 19 ms 2984 KB
1
02_handmake2.in AC 18 ms 3132 KB
1
02_handmake3.in AC 20 ms 3160 KB
1
02_handmake4.in AC 18 ms 3052 KB
1
02_handmake5.in AC 22 ms 3076 KB
1
02_handmake6.in AC 24 ms 2968 KB
1
02_handmake7.in AC 21 ms 2992 KB
1
02_handmake8.in AC 19 ms 3012 KB
1
02_handmake9.in AC 18 ms 3032 KB
1
03_random1.in AC 19 ms 3060 KB
1
03_random2.in AC 20 ms 3076 KB
1
03_random3.in AC 22 ms 3096 KB
1
03_random4.in AC 16 ms 2992 KB
1
03_random5.in AC 20 ms 3140 KB
1
03_random6.in AC 22 ms 3156 KB
1
04_random1.in WA 50 ms 3044 KB
1
04_random2.in AC 20 ms 3064 KB
1
04_random3.in WA 17 ms 3084 KB
1
04_random4.in AC 18 ms 3100 KB
1
04_random5.in AC 18 ms 3116 KB
1
04_random6.in AC 20 ms 3140 KB
1
05_random1.in WA 72 ms 5324 KB
1
05_random2.in WA 75 ms 5324 KB
1
05_random3.in WA 71 ms 5328 KB
1
05_random4.in WA 75 ms 5332 KB
1
06_random1.in AC 34 ms 3044 KB
1
06_random3.in AC 72 ms 5352 KB
1