Submission #00074

ソースコード

?
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <bits/stdc++.h> // clang-format off
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#ifdef ONLINE_JUDGE
#define rep(i,N) for(int i = 0; i < (int)(N); i++)
#define repr(i,N) for(int i = (int)(N) - 1; i >= 0; i--)
#define rep1(i,N) for(int i = 1; i <= (int)(N) ; i++)
#define repr1(i,N) for(int i = (N) ; (int)(i) > 0 ; i--)
#else
#define rep(i,N) for(long long i = 0; i < (long long)(N); i++)
#define repr(i,N) for(long long i = (long long)(N) - 1; i >= 0; i--)
#define rep1(i,N) for(long long i = 1; i <= (long long)(N) ; i++)
#define repr1(i,N) for(long long i = (N) ; (long long)(i) > 0 ; i--)
#endif
using namespace std; void solve();
using ll = long long; template<class T = ll> using V = vector<T>;
using vi = V<int>; using vl = V<>; using vvi = V< V<int> >;
constexpr int inf = 1001001001; constexpr ll infLL = (1LL << 61) - 1;
struct IoSetupNya {IoSetupNya() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(7);} } iosetupnya;
template<typename T, typename U> inline bool amin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template<typename T, typename U> inline bool amax(T &x, U y) { return (x < y) ? (x = y, true) : false; }
template<typename T, typename U> ostream& operator <<(ostream& os, const pair<T, U> &p) { os << p.first << " " << p.second; return os; }
template<typename T, typename U> istream& operator >>(istream& is, pair<T, U> &p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator <<(ostream& os, const vector<T> &v) { int s = (int)v.size(); for(int i=0;i<s;i++) os << (i ? " " : "") << v[i]; return os; }
template<typename T> istream& operator >>(istream& is, vector<T> &v) { for(auto &x : v) is >> x; return is; }
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#ifdef NyaanDebug
#include "NyaanDebug.h"
#define trc(...) do { cerr << #__VA_ARGS__ << " = "; dbg_out(__VA_ARGS__);} while(0)
#define trca(v,N) do { cerr << #v << " = "; array_out(v , N);} while(0)
#define trcc(v) do { cerr << "name : " << #v << "\n"; int cnt = 0; each(x , v){cerr << (cnt++) << " : "; trc(x); } } while(0)
#else
#define trc(...)
#define trca(...)
#define trcc(...)
int main(){solve();}
#endif
#define inc(...) char __VA_ARGS__; in(__VA_ARGS__)
#define in2(s,t) rep(i,sz(s)){in(s[i] , t[i]);}
#define in3(s,t,u) rep(i,sz(s)){in(s[i] , t[i] , u[i]);}
#define in4(s,t,u,v) rep(i,sz(s)){in(s[i] , t[i] , u[i] , v[i]);}
using vd = V<double>; using vs = V<string>; using vvl = V< V<> >;
template<typename T,typename U>ll ceil(T a,U b){return (a + b - 1) / b;}
using P = pair<int,int>; using vp = V<P>;
constexpr int MOD = /** 1000000007; //*/ 998244353;
// clang-format on
///////////////////////////////////////////////////////////
vector<ll> fac,finv,inv;
void cominit(int MAX) {
MAX++;
fac.resize(MAX , 0);
finv.resize(MAX , 0);
inv.resize(MAX , 0);
fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
// nCk combination
inline long long COM(int n,int k){
if(n < k || k < 0 || n < 0) return 0;
else return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// nPk permutation
inline long long PER(int n,int k){
if (n < k || k < 0 || n < 0) return 0;
else return (fac[n] * finv[n - k]) % MOD;
}
// nHk homogeneous polynomial
inline long long HGP(int n,int k){
if(n == 0 && k == 0) return 1; // depending on problem?
else if(n < 1 || k < 0) return 0;
else return fac[n + k - 1] * (finv[k] * finv[n - 1] % MOD) % MOD;
}
template< int mod >
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int) (1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt< mod >(t);
return (is);
}
static int get_mod() { return mod; }
};
using modint = ModInt< MOD >;
using vm = vector<modint>;
using mint = modint;
void solve(){
ini(K);
ins(S);
cominit(K + 10);
vi cnt(10);
each(c,S) cnt[c - '0']++;
mint ans = 1;
int s = K;
rep(i , 10){
ans = ans * COM(s , cnt[i]);
s -= cnt[i];
}
ans /= K;
trc(ans);
mint nya = 0;
rep(i , 10) nya += mint(i) * cnt[i];
ans *= nya;
ans *= (mint(10).pow(K) - 1) / 9;
out(ans);
}

ステータス

項目 データ
問題 0006 - Swap Digits
ユーザー名 Nyaan
投稿日時 2020-03-02 21:05:37
言語 C++14
状態 Accepted
得点 600
ソースコード長 6443 Byte
最大実行時間 46 ms
最大メモリ使用量 5204 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
input01 AC 30 ms 604 KB
1
input02 AC 41 ms 3380 KB
1
input03 AC 23 ms 636 KB
1
input04 AC 20 ms 592 KB
1
input05 AC 28 ms 672 KB
1
input06 AC 37 ms 756 KB
1
input07 AC 24 ms 704 KB
1
input08 AC 25 ms 656 KB
1
input09 AC 29 ms 736 KB
1
input10 AC 23 ms 688 KB
1
input11 AC 21 ms 644 KB
1
input12 AC 27 ms 592 KB
1
input13 AC 28 ms 680 KB
1
input14 AC 17 ms 760 KB
1
input15 AC 24 ms 700 KB
1
input16 AC 18 ms 776 KB
1
input17 AC 29 ms 596 KB
1
input18 AC 27 ms 672 KB
1
input19 AC 25 ms 724 KB
1
input20 AC 20 ms 924 KB
1
input21 AC 31 ms 720 KB
1
input22 AC 21 ms 780 KB
1
input23 AC 30 ms 848 KB
1
input24 AC 21 ms 748 KB
1
input25 AC 23 ms 924 KB
1
input26 AC 21 ms 892 KB
1
input27 AC 25 ms 936 KB
1
input28 AC 24 ms 936 KB
1
input29 AC 21 ms 804 KB
1
input30 AC 24 ms 840 KB
1
input31 AC 25 ms 836 KB
1
input32 AC 19 ms 860 KB
1
input33 AC 23 ms 1432 KB
1
input34 AC 46 ms 2148 KB
1
input35 AC 21 ms 1780 KB
1
input36 AC 21 ms 1700 KB
1
input37 AC 24 ms 1156 KB
1
input38 AC 31 ms 1844 KB
1
input39 AC 21 ms 992 KB
1
input40 AC 30 ms 2724 KB
1
input41 AC 23 ms 1432 KB
1
input42 AC 28 ms 1732 KB
1
input43 AC 32 ms 2720 KB
1
input44 AC 30 ms 1928 KB
1
input45 AC 41 ms 2216 KB
1
input46 AC 46 ms 3276 KB
1
input47 AC 23 ms 3424 KB
1
input48 AC 21 ms 2868 KB
1
input49 AC 22 ms 2732 KB
1
input50 AC 41 ms 4200 KB
1
input51 AC 26 ms 4284 KB
1
input52 AC 28 ms 4356 KB
1
input53 AC 24 ms 4556 KB
1
input54 AC 25 ms 4628 KB
1
input55 AC 23 ms 4704 KB
1
input56 AC 20 ms 3492 KB
1
input57 AC 21 ms 2716 KB
1
input58 AC 25 ms 2992 KB
1
input59 AC 24 ms 3200 KB
1
input60 AC 26 ms 4540 KB
1
input61 AC 29 ms 4060 KB
1
input62 AC 22 ms 3312 KB
1
input63 AC 28 ms 2748 KB
1
input64 AC 26 ms 5204 KB
1
input65 AC 26 ms 4584 KB
1
input66 AC 23 ms 3744 KB
1
input67 AC 23 ms 5068 KB
1
input68 AC 21 ms 3296 KB
1
input69 AC 19 ms 3764 KB
1
input70 AC 18 ms 2924 KB
1
input_sample01 AC 28 ms 3052 KB
1
input_sample02 AC 33 ms 3132 KB
1
input_sample03 AC 22 ms 3084 KB
1
input_sample04 AC 21 ms 3040 KB
1