| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 10/13 | O | O | . | . | Ø | O | O | Ø | O | Ø | O | O | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
A
题目描述
签到题。
解题思路
solved by qxforever
AC代码 - by qxforever
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
using namespace std;
using ll = long long;
using pii = pair<int, int>;
void _debug() {
std::cerr << std::endl;
}
template <typename T, typename... U> void _debug(T t, U... args) {
std::cerr << " " << t;
_debug(args...);
}
const int maxn = 1e6 + 10;
void solve() {
ll n;
scanf("%lld", &n);
ll ans = 0;
if (n <= 100) {
for (int i = 1; i <= n; i++) {
if (i % 2 == 1 && 3 * i + 1 > n) ans++;
if (i + i > n) ans++;
}
printf("%lld\n", ans);
return;
}
int low = n / 2;
ans += n - low;
debug(ans);
// n = 2 * x + 1
int L = 0, R = n;
while (R - L > 1) {
debug(L, R);
int mid = (L + R) >> 1;
ll x = mid * 2 + 1;
debug(x);
if (3 * x + 1 > n)
R = mid;
else
L = mid;
}
debug(L);
ans += (n + 1) / 2 - L - 1;
printf("%lld\n", ans);
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
B
题目描述
$n\le 100$ 个长度不超过 $12$ 的小写英文字母串，每个串代表第 $i$ 个系统的循环节。
对于一个时间，依次将每个系统的字符串联起来（比较抽象，建议看样例），得到一个无限串 $s$，问 $s$ 中最短能覆盖全部出现过字母的长度。
无限串是个循环节不超过 $\text{lcm}(1,2,\cdots 12)$ 的循环串，故展开到 $2\text{lcm}$ 之后双指针线性扫一遍即可。
解题思路
solved by nikkukun
AC代码 - by nikkukun
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
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;
const int N = 100;
const int LCM = 27720;
const int M = N * LCM * 2 + 5;
const int L = 12 + 2;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
char s[N][LCM];
char ss[M];
int cnt[N];
void solve() {
memset(cnt, 0, sizeof(cnt));
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s", s[i]);
int len = strlen(s[i]);
for (int j = 0; j < len; j++)
cnt[s[i][j] - 'a']++;
for (int j = len; j < LCM; j++)
s[i][j] = s[i][j % len];
s[i][LCM] = '\0';
}
for (int i = 0; i < LCM * n * 2; i++) {
int x = i % n;
int y = i / n;
if (y >= LCM) y -= LCM;
ss[i] = s[x][y];
}
int cntSum = 0;
for (int i = 0; i < 26; i++)
cntSum += cnt[i] > 0;
memset(cnt, 0, sizeof(cnt));
int L = 0, R = 0;
int ans = INF;
int cntNow = 0;
// [0, 0)
int LIM1 = LCM * n;
int LIM2 = LCM * n * 2;
while (L < LIM1) {
while (R < LIM2 && cntNow < cntSum) {
int c = ss[R] - 'a';
if (cnt[c] == 0) {
cntNow++;
}
cnt[c]++;
R++;
}
if (cntNow == cntSum)
ans = min(ans, R - L);
int c = ss[L] - 'a';
cnt[c]--;
if (cnt[c] == 0) {
cntNow--;
}
L++;
}
printf("%d\n", ans);
}
// 27720
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}
C
题目描述
解题思路
AC代码
2
D
题目描述
解题思路
AC代码
2
E
题目描述
$f(i,j)=\left\{\begin{aligned}&0,&i=0\\ &a,&i=1\\ &bf(i-1,j)+cf(i-2,j),&2\le i\le j\\ &df(i-1,j)+ef(i-2,j),&i>j\end{aligned}\right.$
求 $\sum_{i=1}^{n}\sum_{j=1}^{n}\binom{i+j}{j}f(i+j,j)$
$n\le 1e5$
解题思路
（赛中与 nikkukun 想的比较麻烦的解法）
考虑生成函数：对于满足 $c_i=dc_{i-1}+ec_{i-2},i\ge 2$ 的数列，设生成函数为 $F(x)$，有
$F(x)=c_0+c_1x+dx(F(x)-c_0)+ex^2F(x)$
解得 $F(x)=\frac{c_0+(c_1-dc_0)x}{1-dx-ex^2}$
对于求和式，固定一个 $i$，则 $f(i+j,j)$ 为 $a_{0,i},a_{1,i}$ 为前两项、$d,e$ 为递推系数的线性递推第 $j$ 项。 $a_{0,i},a_{1,i}$ 容易线性求出，是首项 $0,a$，$b,c$ 为递推系数的线性递推第 $i$ 项。
于是根据上面的生成函数，$f(i+j,j)=[x^j](\frac{a_{0,i}+(a_{1,i}-da_{0,i})x}{1-dx-ex^2})$。
设 $p=\frac{1}{1-dx-ex^2}\bmod x^{n+1}$，$a0_{i}=a_{0,i},a1_{i}=a_{1,i-da_{0,i}}$，则 $f(i+j,j)=[x^j]pa0_{i}+(px)a1_{x}$
于是可以卷积，求出 $\sum_{i+j=k}\frac{k!}{i!j!}(p\ast a0+(px)\ast a1)$ 即为答案。
复杂度 $O(kn\log n)$，$k=2$，用热心的板子可以卡过。
AC代码
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
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
typedef long long ll;
using namespace std;
const ll mod=998244353;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353U;
constexpr unsigned MO2 = 2U * MO;
constexpr int FFT_MAX = 23;
using Mint = ModInt<MO>;
constexpr Mint FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 911660635U, 372528824U, 929031873U, 452798380U, 922799308U, 781712469U, 476477967U, 166035806U, 258648936U, 584193783U, 63912897U, 350007156U, 666702199U, 968855178U, 629671588U, 24514907U, 996173970U, 363395222U, 565042129U, 733596141U, 267099868U, 15311432U};
constexpr Mint INV_FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 86583718U, 509520358U, 337190230U, 87557064U, 609441965U, 135236158U, 304459705U, 685443576U, 381598368U, 335559352U, 129292727U, 358024708U, 814576206U, 708402881U, 283043518U, 3707709U, 121392023U, 704923114U, 950391366U, 428961804U, 382752275U, 469870224U};
constexpr Mint FFT_RATIOS[FFT_MAX] = {911660635U, 509520358U, 369330050U, 332049552U, 983190778U, 123842337U, 238493703U, 975955924U, 603855026U, 856644456U, 131300601U, 842657263U, 730768835U, 942482514U, 806263778U, 151565301U, 510815449U, 503497456U, 743006876U, 741047443U, 56250497U, 867605899U};
constexpr Mint INV_FFT_RATIOS[FFT_MAX] = {86583718U, 372528824U, 373294451U, 645684063U, 112220581U, 692852209U, 155456985U, 797128860U, 90816748U, 860285882U, 927414960U, 354738543U, 109331171U, 293255632U, 535113200U, 308540755U, 121186627U, 608385704U, 438932459U, 359477183U, 824071951U, 103369235U};
// as[rev(i)] <- \sum_j \zeta^(ij) as[j]
void fft(Mint *as, int n) {
assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
int m = n;
if (m >>= 1) {
for (int i = 0; i < m; ++i) {
const unsigned x = as[i + m].x; // < MO
as[i + m].x = as[i].x + MO - x; // < 2 MO
as[i].x += x; // < 2 MO
}
}
if (m >>= 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + m; ++i) {
const unsigned x = (prod * as[i + m]).x; // < MO
as[i + m].x = as[i].x + MO - x; // < 3 MO
as[i].x += x; // < 3 MO
}
prod *= FFT_RATIOS[__builtin_ctz(++h)];
}
}
for (; m; ) {
if (m >>= 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + m; ++i) {
const unsigned x = (prod * as[i + m]).x; // < MO
as[i + m].x = as[i].x + MO - x; // < 4 MO
as[i].x += x; // < 4 MO
}
prod *= FFT_RATIOS[__builtin_ctz(++h)];
}
}
if (m >>= 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + m; ++i) {
const unsigned x = (prod * as[i + m]).x; // < MO
as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x; // < 2 MO
as[i + m].x = as[i].x + MO - x; // < 3 MO
as[i].x += x; // < 3 MO
}
prod *= FFT_RATIOS[__builtin_ctz(++h)];
}
}
}
for (int i = 0; i < n; ++i) {
as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x; // < 2 MO
as[i].x = (as[i].x >= MO) ? (as[i].x - MO) : as[i].x; // < MO
}
}
// as[i] <- (1/n) \sum_j \zeta^(-ij) as[rev(j)]
void invFft(Mint *as, int n) {
assert(!(n & (n - 1))); assert(1 <= n); assert(n <= 1 << FFT_MAX);
int m = 1;
if (m < n >> 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + m; ++i) {
const unsigned long long y = as[i].x + MO - as[i + m].x; // < 2 MO
as[i].x += as[i + m].x; // < 2 MO
as[i + m].x = (prod.x * y) % MO; // < MO
}
prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
}
m <<= 1;
}
for (; m < n >> 1; m <<= 1) {
Mint prod = 1U;
for (int h = 0, i0 = 0; i0 < n; i0 += (m << 1)) {
for (int i = i0; i < i0 + (m >> 1); ++i) {
const unsigned long long y = as[i].x + MO2 - as[i + m].x; // < 4 MO
as[i].x += as[i + m].x; // < 4 MO
as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x; // < 2 MO
as[i + m].x = (prod.x * y) % MO; // < MO
}
for (int i = i0 + (m >> 1); i < i0 + m; ++i) {
const unsigned long long y = as[i].x + MO - as[i + m].x; // < 2 MO
as[i].x += as[i + m].x; // < 2 MO
as[i + m].x = (prod.x * y) % MO; // < MO
}
prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];
}
}
if (m < n) {
for (int i = 0; i < m; ++i) {
const unsigned y = as[i].x + MO2 - as[i + m].x; // < 4 MO
as[i].x += as[i + m].x; // < 4 MO
as[i + m].x = y; // < 4 MO
}
}
const Mint invN = Mint(n).inv();
for (int i = 0; i < n; ++i) {
as[i] *= invN;
}
}
void fft(vector<Mint> &as) {
fft(as.data(), as.size());
}
void invFft(vector<Mint> &as) {
invFft(as.data(), as.size());
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
// inv: log, exp, pow
constexpr int LIM_INV = 1 << 20; // @
// polyWork0: *, inv, div, divAt, log, exp, pow, sqrt
// polyWork1: inv, div, divAt, log, exp, pow, sqrt
// polyWork2: divAt, exp, pow, sqrt
// polyWork3: exp, pow, sqrt
static constexpr int LIM_POLY = 1 << 20; // @
static_assert(LIM_POLY <= 1 << FFT_MAX, "Poly: LIM_POLY <= 1 << FFT_MAX must hold.");
static Mint polyWork0[LIM_POLY], polyWork1[LIM_POLY], polyWork2[LIM_POLY], polyWork3[LIM_POLY];
struct Poly : public vector<Mint> {
Poly() {}
explicit Poly(int n) : vector<Mint>(n) {}
Poly(const vector<Mint> &vec) : vector<Mint>(vec) {}
Poly(std::initializer_list<Mint> il) : vector<Mint>(il) {}
int size() const { return vector<Mint>::size(); }
int ord() const { for (int i = 0; i < size(); ++i) if ((*this)[i]) return i; return -1; }
int deg() const { for (int i = size(); --i >= 0; ) if ((*this)[i]) return i; return -1; }
Poly &operator+=(const Poly &fs) {
if (size() < fs.size()) resize(fs.size());
for (int i = 0; i < fs.size(); ++i) (*this)[i] += fs[i];
return *this;
}
Poly &operator-=(const Poly &fs) {
if (size() < fs.size()) resize(fs.size());
for (int i = 0; i < fs.size(); ++i) (*this)[i] -= fs[i];
return *this;
}
// 3 E(|t| + |f|)
Poly &operator*=(const Poly &fs) {
if (empty() || fs.empty()) return *this = {};
const int nt = size(), nf = fs.size();
int n = 1;
for (; n < nt + nf - 1; n <<= 1) {}
assert(n <= LIM_POLY);
resize(n);
fft(data(), n); // 1 E(n)
memcpy(polyWork0, fs.data(), nf * sizeof(Mint));
memset(polyWork0 + nf, 0, (n - nf) * sizeof(Mint));
fft(polyWork0, n); // 1 E(n)
for (int i = 0; i < n; ++i) (*this)[i] *= polyWork0[i];
invFft(data(), n); // 1 E(n)
resize(nt + nf - 1);
return *this;
}
Poly &operator*=(const Mint &a) {
for (int i = 0; i < size(); ++i) (*this)[i] *= a;
return *this;
}
Poly &operator/=(const Mint &a) {
const Mint b = a.inv();
for (int i = 0; i < size(); ++i) (*this)[i] *= b;
return *this;
}
Poly operator+() const { return *this; }
Poly operator-() const {
Poly fs(size());
for (int i = 0; i < size(); ++i) fs[i] = -(*this)[i];
return fs;
}
Poly operator+(const Poly &fs) const { return (Poly(*this) += fs); }
Poly operator-(const Poly &fs) const { return (Poly(*this) -= fs); }
Poly operator*(const Poly &fs) const { return (Poly(*this) *= fs); }
Poly operator*(const Mint &a) const { return (Poly(*this) *= a); }
Poly operator/(const Mint &a) const { return (Poly(*this) /= a); }
friend Poly operator*(const Mint &a, const Poly &fs) { return fs * a; }
// 10 E(n)
// f <- f - (t f - 1) f
Poly inv(int n) const {
assert(!empty()); assert((*this)[0]); assert(1 <= n);
assert(n == 1 || 1 << (32 - __builtin_clz(n - 1)) <= LIM_POLY);
Poly fs(n);
fs[0] = (*this)[0].inv();
for (int m = 1; m < n; m <<= 1) {
memcpy(polyWork0, data(), min(m << 1, size()) * sizeof(Mint));
memset(polyWork0 + min(m << 1, size()), 0, ((m << 1) - min(m << 1, size())) * sizeof(Mint));
fft(polyWork0, m << 1); // 2 E(n)
memcpy(polyWork1, fs.data(), min(m << 1, n) * sizeof(Mint));
memset(polyWork1 + min(m << 1, n), 0, ((m << 1) - min(m << 1, n)) * sizeof(Mint));
fft(polyWork1, m << 1); // 2 E(n)
for (int i = 0; i < m << 1; ++i) polyWork0[i] *= polyWork1[i];
invFft(polyWork0, m << 1); // 2 E(n)
memset(polyWork0, 0, m * sizeof(Mint));
fft(polyWork0, m << 1); // 2 E(n)
for (int i = 0; i < m << 1; ++i) polyWork0[i] *= polyWork1[i];
invFft(polyWork0, m << 1); // 2 E(n)
for (int i = m, i0 = min(m << 1, n); i < i0; ++i) fs[i] = -polyWork0[i];
}
return fs;
}
};
int f[N],inv[N],fac[N];
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
int main(){
int i,n,a,b,c,d,e;
fac[0]=1;
for(i=1;i<N;i++)fac[i]=1LL*fac[i-1]*i%mod;
inv[N-1]=qp(fac[N-1],mod-2);
for(i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1LL)%mod;
scanf("%*d");
while(~scanf("%d%d%d%d%d%d",&n,&a,&b,&c,&d,&e)){
f[0]=0,f[1]=a;
for(i=2;i<=n;i++)f[i]=(1LL*f[i-1]*b+1LL*f[i-2]*c)%mod;
Poly a0(n+1),a1(n+1);
a0[0]=a1[0]=0;
for(i=1;i<=n;i++){
ll nxt=1LL*f[i]*d+1LL*f[i-1]*e;
a1[i]=1LL*(mod+nxt%mod-1LL*d*f[i]%mod)*inv[i]%mod;
a0[i]=1LL*f[i]*inv[i]%mod;
}
Poly p({1,mod-d,mod-e});
p=p.inv(n+1);
Poly q(p);
for(i=p.size()-1;i-1>=0;i--)q[i]=p[i-1];
p[0]=q[0]=0;
for(i=1;i<=n;i++){
p[i]*=inv[i];
q[i]*=inv[i];
}
Poly r=p*a0+q*a1;
ll ans=0;
for(i=2;i<=n+n;i++){
ans=(ans+1LL*r[i].x*fac[i]%mod)%mod;
}
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}
解题思路2
另外有一种 $O(nk^3)$ 的做法。
设转移矩阵 $A=\left(\begin{matrix}b,c\\1,0\end{matrix}\right),B=\left(\begin{matrix}d,e\\1,0\end{matrix}\right)$，每个 $i$ 对应的转移矩阵 $f(i)=\sum_{j=1}^{n}B^jA^{i-1}\binom{i+j}{i}$ ，对应贡献为 $f(i)\cdot \left(\begin{aligned}a\\ 0\end{aligned}\right)$。考虑根据组合公式递推这个转移矩阵。
$\begin{aligned}f(i+1)&=\sum_{j=1}^{n}B^jA^i\binom{i+j+1}{i+1}\\&=\sum_{j=1}^{n}B^jA^{i-1}\binom{i+j}{i}A+\sum_{j=1}^{n}B^jA^{i}\binom{i+j}{i+1}\\&=f(i)A+B\sum_{j=0}^{n-1}B^jA^{i}\binom{i+j+1}{i+1}\\&=f(i)A+Bf(i+1)-B^{n+1}A^i\binom{i+n+1}{i+1}+BA^{i})\end{aligned}$
$f(i+1)=(I-B)^{-1}(f(i)A-B^{n+1}A^i\binom{i+n+1}{i+1}+BA^{i})$
AC代码
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
typedef long long ll;
using namespace std;
const int mod=998244353;
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
int fac[N],invf[N];
int C(int n,int m){
assert(n>=m&&m>=0);
return 1LL*fac[n]*invf[m]%mod*invf[n-m]%mod;
}
namespace gauss{
int inv[K][K],n=2;
int calc_inv_matrix(int a[][K]){
int i,j,k;
for(i=0;i<n;i++)for(j=0;j<n;j++)inv[i][j]=(i==j);
for(i=0;i<n;i++){
if(!a[i][i]){
int flag=0;
for(j=i+1;j<n;j++)
if(a[j][i]){
for(k=0;k<n;k++)swap(a[j][k],a[i][k]);
swap(inv[j],inv[i]);
flag=1;
break;
}
if(!flag)return 0;
}
ll coe=qp(a[i][i],mod-2);
for(j=0;j<n;j++)
inv[i][j]=inv[i][j]*coe%mod,
a[i][j]=a[i][j]*coe%mod;
for(j=0;j<n;j++){
if(i==j)continue;
coe=a[j][i];
for(k=0;k<n;k++){
inv[j][k]=(inv[j][k]-1LL*inv[i][k]*coe%mod+mod)%mod,
a[j][k]=(a[j][k]-1LL*a[i][k]*coe%mod+mod)%mod;
}
}
}
return 1;
}
}
typedef struct Matrix{
int a[K][K];
Matrix(){
memset(a,0,sizeof(a));
}
Matrix(int x,int y){
a[0][0]=x;a[0][1]=y;
a[1][0]=1;a[1][1]=0;
}
Matrix(int x,int y,int z,int w){
a[0][0]=x;a[0][1]=y;
a[1][0]=z;a[1][1]=w;
}
Matrix operator*(const int&x){
int i,j;
Matrix res;
for(i=0;i<K;i++)
for(j=0;j<K;j++)
res.a[i][j]=1LL*a[i][j]*x%mod;
return res;
}
Matrix operator*(const Matrix&b){
int i,j,k;
Matrix res;
for(i=0;i<K;i++){
for(j=0;j<K;j++){
res.a[i][j]=0;
for(k=0;k<K;k++)
res.a[i][j]=(res.a[i][j]+1LL*a[i][k]*b.a[k][j]%mod)%mod;
}
}
return res;
}
Matrix operator+(const Matrix&b){
int i,j;
Matrix res;
for(i=0;i<K;i++)
for(j=0;j<K;j++)
res.a[i][j]=(a[i][j]+b.a[i][j])%mod;
return res;
}
Matrix operator-(const Matrix&b){
int i,j;
Matrix res;
for(i=0;i<K;i++)
for(j=0;j<K;j++)
res.a[i][j]=(a[i][j]+mod-b.a[i][j])%mod;
return res;
}
}mt;
mt f[N],apw[N],bpw[N];
using namespace gauss;
int main(){
int i,j;
int T,n,a,b,c,d,e;
fac[0]=1;
for(i=1;i<N;i++)fac[i]=1LL*fac[i-1]*i%mod;
invf[N-1]=qp(fac[N-1],mod-2);
for(i=N-2;i>=0;i--)invf[i]=invf[i+1]*(i+1LL)%mod;
scanf("%d",&T);
while(T--){
scanf("%d%d%d%d%d%d",&n,&a,&b,&c,&d,&e);
mt A(b,c),B(d,e),I(1,0,0,1);
apw[0]=bpw[0]=I;
assert(calc_inv_matrix((I-B).a));
mt iv(inv[0][0],inv[0][1],inv[1][0],inv[1][1]); // (I-B)^-1
for(i=1;i<=n+1;i++)apw[i]=apw[i-1]*A,bpw[i]=bpw[i-1]*B;
f[1]=mt();
for(j=1;j<=n;j++)f[1]=f[1]+bpw[j]*(j+1);
for(i=2;i<=n;i++)f[i]=iv*(f[i-1]*A-bpw[n+1]*apw[i-1]*C(i+n,i)+B*apw[i-1]);
int ans=0;
for(i=1;i<=n;i++)ans=(ans+1LL*f[i].a[0][0]*a%mod)%mod;
printf("%d\n",ans);
}
return 0;
}
F
题目描述
求 $k$ 和一个长度为 $k$ 的序列 $a_i$，要求 $a_i=1$ 或 $-1$，且 $\sum_{i=1}^{k}a_ii^2=n$
解题思路
solved by qxforever
发现连续四项 $1,-1,-1,1$ 能凑出来一个 $4$，根据余数讨论一下即可。
AC代码 - by qxforever
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
using namespace std;
using ll = long long;
using pii = pair<int, int>;
void _debug() {
std::cerr << std::endl;
}
template <typename T, typename... U> void _debug(T t, U... args) {
std::cerr << " " << t;
_debug(args...);
}
const int maxn = 1e6 + 10;
char s[maxn];
char c[3] = "01";
void get4(int x) {
s[x] = s[x + 3] = '1';
s[x + 1] = s[x + 2] = '0';
s[x + 4] = 0;
}
void solve() {
int n;
cin >> n;
// n = rand() % 50 + 1;
int m = n % 4;
if (m == 0) {
for (int i = 1; i <= n; i += 4) {
get4(i);
}
}
else if (m == 1) {
s[1] = '1';
s[2] = 0;
for (int i = 2; i <= n; i += 4) {
get4(i);
}
}
else if (m == 2) {
s[1] = s[2] = s[3] = '0';
s[4] = '1';
s[5] = 0;
for (int i = 5; i <= n + 2; i += 4) {
get4(i);
}
}
else {
s[1] = '0';
s[2] = '1';
s[3] = 0;
for (int i = 3; i < n; i += 4) {
get4(i);
}
}
// int sum = 0;
// for (int i = 1; s[i]; i++) {
// int op = s[i] == '1' ? 1 : -1;
// sum += 1ll * i * i * op;
// }
// debug(sum, n);
// assert(sum == n);
int len = strlen(s + 1);
// debug(len);
assert(len <= n + 2);
printf("%d\n", len);
printf("%s\n", s + 1);
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
G
题目描述
设 $g(x)$ 表示 $x$ 的数位和。
对 $1\le x\le N$，求出 $f(x)=Ax^2g(x)+Bx^2+Cxg^2(x)+Dxg(x)$ 的最小值。
解题思路
solved by nikkukun
枚举数位和，就是一个二次函数，讨论一下中点和两端即可。
AC代码 - by nikkukun
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
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;
const int N = 1e6 + 5;
const int D = 9 * 6 + 2;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
vector<ll> digits[D];
int dsum[N];
ll getF(ll A, ll B, ll x) {
return x * (A * x + B);
}
int main() {
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
for (int i = 1; i < N; i++) {
dsum[i] = dsum[i / 10] + i % 10;
digits[dsum[i]].push_back(i);
}
int t;
scanf("%d", &t);
while (t--) {
ll a, b, c, d, n;
scanf("%lld%lld%lld%lld%lld", &a, &b, &c, &d, &n);
ll ans = INF_LL;
for (int g = 0; g < D; g++) {
if (digits[g].empty()) continue;
vector<ll> vec;
ll A = (a * g + b);
ll B = (c * g * g + d * g);
if (A != 0) {
ll x0 = -B / (2 * A);
int p = lower_bound(all(digits[g]), x0) - digits[g].begin();
if (p + 1 < digits[g].size() && digits[g][p + 1] <= n)
vec.push_back(digits[g][p + 1]);
if (p < digits[g].size() && digits[g][p] <= n)
vec.push_back(digits[g][p]);
if (p - 1 >= 0 && digits[g][p - 1] <= n)
vec.push_back(digits[g][p - 1]);
}
int q = lower_bound(all(digits[g]), n + 1) - digits[g].begin();
if (q - 1 >= 0 && digits[g][q - 1] <= n)
vec.push_back(digits[g][q - 1]);
if (digits[g][0] <= n)
vec.push_back(digits[g][0]);
for (auto x: vec)
ans = min(ans, getF(A, B, x));
}
ans = min(ans, getF(a * dsum[1] + b, c * dsum[1] * dsum[1] + d * dsum[1], 1));
ans = min(ans, getF(a * dsum[n] + b, c * dsum[n] * dsum[n] + d * dsum[n], n));
printf("%lld\n", ans);
}
return 0;
}
H
题目描述
给一个 $n\le 1e5$ 的排列 $a$，令 $v(l,r)=max_{l\le i<j\le r}\gcd(a_i,a_j)$，对每个 $x\in[1,n]$ 求有多少个 $[l,r]$ 对满足 $v(l,r)=x$。
解题思路
因为是排列，所以总因子数 $O(n\log n)$，考虑从大到小枚举 $\gcd$。
对于固定左端点，记录最大仍未计算贡献的区间右端点，变成了区间置 $\min$、查询区间和的问题，这是经典的 $\text{Segment tree beats}$ 问题，直接维护一下即可。复杂度 $O(n\log^2n)$。
AC代码
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
typedef long long ll;
using namespace std;
ll ans[N];
int n,a[N];
int L[N],R[N],mx[N],cnt[N],se[N],lazy[N];
ll s[N];
void tag(int p,int t){
if(mx[p]>t){
assert(se[p]<t);
s[p]-=1LL*(mx[p]-t)*cnt[p];
lazy[p]=mx[p]=t;
}
}
void pushdown(int p){
int t=lazy[p];
if(t==-1)return;
tag(p<<1,t);
tag(p<<1|1,t);
lazy[p]=-1;
}
void pushup(int p){
s[p]=s[p<<1]+s[p<<1|1];
mx[p]=max(mx[p<<1],mx[p<<1|1]);
if(mx[p<<1]==mx[p<<1|1]){
cnt[p]=cnt[p<<1]+cnt[p<<1|1];
se[p]=max(se[p<<1],se[p<<1|1]);
}else if(mx[p<<1]>mx[p<<1|1]){
cnt[p]=cnt[p<<1];
se[p]=max(se[p<<1],mx[p<<1|1]);
}else{
cnt[p]=cnt[p<<1|1];
se[p]=max(se[p<<1|1],mx[p<<1]);
}
}
void build(int p,int l,int r){
L[p]=l;R[p]=r;
lazy[p]=-1;
if(l==r){
cnt[p]=1;
s[p]=mx[p]=n+1;
se[p]=-1;
return;
}
build(p<<1,l,(l+r)>>1);
build(p<<1|1,((l+r)>>1)+1,r);
pushup(p);
}
void modify_min(int p,int l,int r,int x){
if(l>R[p]||r<L[p]||mx[p]<=x)return;
if(L[p]>=l&&R[p]<=r&&se[p]<x){
tag(p,x);
return;
}
pushdown(p);
modify_min(p<<1,l,r,x);
modify_min(p<<1|1,l,r,x);
pushup(p);
}
ll query_sum(int p,int l,int r){
if(r<L[p]||l>R[p])return 0;
if(L[p]>=l&&R[p]<=r)return s[p];
pushdown(p);
return query_sum(p<<1,l,r)+query_sum(p<<1|1,l,r);
}
int main(){
int T,i,j;
static vector<int>v[N];
for(i=1;i<N;i++)
for(j=i;j<N;j+=i)
v[j].pb(i);
scanf("%d",&T);
while(T--){
scanf("%d",&n);
static vector<int>g[N];
for(i=1;i<=n;i++)g[i].clear();
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
for(auto x:v[a[i]])g[x].pb(i);
}
build(1,1,n);
for(i=n;i>=1;i--){
ans[i]=0;
int last=1;
ll before=s[1];
for(j=0;j+1<g[i].size();j++){
int nxt=g[i][j],val=g[i][j+1];
modify_min(1,last,nxt,val);
last=nxt+1;
}
ans[i]=before-s[1];
}
for(i=1;i<=n;i++)printf("%lld\n",ans[i]);
}
return 0;
}
I
题目描述
签到题。
解题思路
solved by nikkukun
AC代码 - by nikkukun
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
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pint;
typedef tuple<int, int, int> tint;
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
char s[N];
void solve() {
int n;
scanf("%d", &n);
scanf("%s", s + 1);
map<pint, int> st;
st[{0, 0}] = 1;
ll ans = 0;
int x = 0, y = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == 'U') x++;
if (s[i] == 'D') x--;
if (s[i] == 'L') y++;
if (s[i] == 'R') y--;
ans += st[{x, y}];
st[{x, y}]++;
}
cout << ans << endl;
}
int main() {
int t;
scanf("%d", &t);
while (t--) solve();
return 0;
}
J
题目描述
给一个 $n\le 500,m\le 1e4$ 无向简单图，每个边有两个权值 $(a,b\le 100)$，初始根据 $w$ 序列的加权概率在 $i$ 出发，进行完全等概率的随机游走，但只要到达 $n$ 就立刻停止。
第 $t$ 时刻，经过一个边 $(a,b)$ 时，获得 $\max(\lfloor\frac a{2^{t-1}}\rfloor,b)$ 的分数。问期望分数。
需要支持两种修改操作：
- $(x,y,a,b)$，修改 $(x,y)$ 之间的边为 $(a,b)$
- $w[x]=c$，这种修改操作次数不超过 $n$
解题思路
先不考虑修改。对于 $t>6$，每条边的贡献都成为了 $b$。于是先不讨论 $a$。
设 $E_i$ 表示经过 $i$ 次数的期望，则一条边 $(x,y,b)$ 对答案的贡献是 $b(\frac {E_x}{deg_x}+\frac{E_y}{deg_y})$。可以列出方程：$E_i=p_i+\sum_{j\in n(i)}\frac{E_j}{deg_j}$，其中 $n(i)$ 表示 $i$ 的邻域。这可以高斯消元解出。由于要支持修改，发现系数矩阵是固定的，所以可以求系数矩阵的逆 $inv$，每次 $p$ 改变后 $E=inv\times p$。
考虑 $t\le 6$ 的情况，暴力 $dp$，设 $P(t,i)$ 表示 $t$ 时刻到了 $i$ 的概率，用类似的方式可以求出每条边的贡献。因此对应地将 $E_i$ 减掉 $t\le 6$ 部分贡献即可。
对于第一种操作，可 $O(1)$ 求出；第二种操作 $O(6m)$ 求出。
AC代码
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
typedef long long ll;
using namespace std;
const int mod=998244353;
int deg[N],a[N][N],inv[N][N],n,m,q;
pii id[N][N];
vector<pair<int,pii>>G[N];
ll qp(ll a,int p){
ll ans=1;
for(;p;p>>=1,a=a*a%mod)if(p&1)ans=ans*a%mod;
return ans;
}
int calc_inv_matrix(int a[][N]){
int i,j,k;
for(i=1;i<=n;i++)for(j=1;j<=n;j++)inv[i][j]=(i==j);
for(i=1;i<=n;i++){
if(!a[i][i]){
int flag=0;
for(j=i+1;j<=n;j++)
if(a[j][i]){
for(k=1;k<=n;k++)swap(a[j][k],a[i][k]);
swap(inv[j],inv[i]);
flag=1;
break;
}
if(!flag)return 0;
}
ll coe=qp(a[i][i],mod-2);
for(j=1;j<=n;j++)
inv[i][j]=inv[i][j]*coe%mod,
a[i][j]=a[i][j]*coe%mod;
for(j=1;j<=n;j++){
if(i==j)continue;
coe=a[j][i];
for(k=1;k<=n;k++){
inv[j][k]=(inv[j][k]-1LL*inv[i][k]*coe%mod+mod)%mod,
a[j][k]=(a[j][k]-1LL*a[i][k]*coe)%mod;
}
}
}
return 1;
}
int w[N],p[N],e[N],P[7][N];
int invs[N]; // 1 / i
int ans;
int calc(int x,int y){
auto pr=G[x][id[x][y].fi].se;
int i,a=pr.fi,b=pr.se,res=0;
for(i=0;i<=6;i++){
res=(res+max(a,b)*(1LL*P[i][x]*invs[deg[x]]%mod+1LL*P[i][y]*invs[deg[y]]%mod)%mod)%mod;
a/=2;
}
res=(res+b*(1LL*e[x]*invs[deg[x]]%mod+1LL*e[y]*invs[deg[y]]%mod))%mod;
return res;
}
void calc_prob(){
int i,j;
ll s=0;
for(i=1;i<n;i++)s+=w[i];
s=qp(s%mod,mod-2);
for(i=1;i<n;i++)p[i]=w[i]*s%mod;
// P[t][i]: prob of at t sec, at i
for(i=1;i<n;i++)P[0][i]=p[i];
for(j=1;j<=6;j++){
for(i=1;i<n;i++){
P[j][i]=0;
for(auto pr:G[i]){
int q=pr.fi;
P[j][i]=(P[j][i]+1LL*P[j-1][q]*invs[deg[q]])%mod;
}
}
}
// inv * p = e
memset(e,0,sizeof(int)*(n+1));
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
e[i]=(e[i]+1LL*inv[i][j]*p[j])%mod;
// e: > 6 step, expected cnt passing i
for(i=0;i<=6;i++)
for(j=1;j<=n;j++)
e[j]=(e[j]+mod-P[i][j])%mod;
ans=0;
for(i=1;i<=n;i++){
for(auto pr:G[i]){
int q=pr.fi;
if(q<i)continue;
ans=(ans+calc(i,q))%mod;
}
}
}
void init(){
int i,j;
for(i=1;i<=n;i++)invs[i]=qp(i,mod-2);
memset(a,0,sizeof(a));
for(i=1;i<=n;i++){
a[i][i]=1;
if(i==n)break;
for(j=1;j<=n;j++){
if(id[i][j].fi==-1)continue;
a[i][j]=mod-invs[deg[j]];
}
}
assert(calc_inv_matrix(a));
calc_prob();
}
int main(){
int i,j;
scanf("%d%d%d",&n,&m,&q);
for(i=1;i<n;i++)scanf("%d",&w[i]);
for(i=1;i<=n;i++)for(j=1;j<=n;j++)id[i][j]=mp(-1,-1);
for(i=0;i<m;i++){
int x,y,a,b;
scanf("%d%d%d%d",&x,&y,&a,&b);
G[x].pb(mp(y,mp(a,b)));
G[y].pb(mp(x,mp(a,b)));
id[x][y]=mp(G[x].size()-1,G[y].size()-1);
id[y][x]=mp(G[y].size()-1,G[x].size()-1);
deg[x]++;deg[y]++;
}
init();
printf("%d\n",ans);
while(q--){
int op,x,y,a,b,c;
scanf("%d",&op);
if(op==1){
scanf("%d%d%d%d",&x,&y,&a,&b);
ans=(ans+mod-calc(x,y))%mod;
G[x][id[x][y].fi].se=G[y][id[x][y].se].se=mp(a,b);
ans=(ans+calc(x,y))%mod;
}else{
scanf("%d%d",&x,&c);
w[x]=c;
calc_prob();
}
printf("%d\n",ans);
}
return 0;
}
K
题目描述
$n\times m$ 打砖块，每次消耗一发子弹打一个裸露的砖块，一些砖块可能会给一个子弹奖励。每个砖块都有一定分数，问 $k$ 发子弹最多能获得多少分。$n,m,k\le 200$
解题思路
solved by qxforever
讨论一下每列最后一发打到了奖励砖块还是非奖励砖块，前 $i$ 列，用了 $j$ 子弹，设为 $f(i,j,0/1)$ 就可以 $DP$ 了。
AC代码 - by qxforever
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
using namespace std;
using ll = long long;
using pii = pair<int, int>;
void _debug() {
std::cerr << std::endl;
}
template <typename T, typename... U> void _debug(T t, U... args) {
std::cerr << " " << t;
_debug(args...);
}
const int maxn = 210;
int f[maxn][maxn], g[maxn][maxn];
int a[maxn][maxn], c[maxn][maxn];
bool b[maxn][maxn];
char s[10];
pii operator+(const pii& a, const pii& b) {
return make_pair(a.first + b.first, a.second + b.second);
}
void solve() {
int n, m, w, p;
scanf("%d%d%d", &n, &m, &w);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &p);
a[j][i] = p;
scanf("%s", s);
b[j][i] = s[0] == 'Y';
}
}
swap(n, m);
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= w; j++) f[i][j] = 0, g[i][j] = -1e9;
}
for (int i = 1; i <= n; i++) {
int cnt = 0;
int sum = 0;
for (int k = 0; k <= w; k++) f[i + 1][k] = f[i][k], g[i + 1][k] = g[i][k];
bool used = false;
for (int j = m; j >= 1; j--) {
sum += a[i][j];
cnt += !b[i][j];
used = b[i][j];
// debug(i, j, sum, cnt);
for (int k = 0; k + cnt <= w; k++) {
if (k + cnt == w && used)
;
else
f[i + 1][k + cnt] = max(f[i + 1][k + cnt], f[i][k] + sum);
if (!used) {
g[i + 1][k + cnt] = max(g[i + 1][k + cnt], f[i][k] + sum);
}
g[i + 1][k + cnt] = max(g[i + 1][k + cnt], g[i][k] + sum);
}
}
}
int ans = 0;
for (int i = 1; i <= n + 1; i++) {
for (int j = 0; j <= w; j++) {
ans = max(ans, f[i][j]);
ans = max(ans, g[i][j]);
debug(i, j, g[i][j]);
}
}
printf("%d\n", ans);
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
/*
3 2 1
3 Y 2 Y
4 Y 1 N
2 Y 8 Y
1 7 1
1 Y 2 N 3 Y 1 N 1 N 4 Y 1 N
*/
L
题目描述
给定 $|P|\le 1e5$ 个质数，玩游戏。有 $k$ 个石子的时候，可以任意找一个不能整除 $k$ 的质数并拿走 $k\bmod p$ 个石子，当不能拿的时候游戏结束。
对于每一个 $1\le i\le n\le 2e6$，求出初始有 $i$ 个石子的时候，至少多少步才能玩完。
解题思路
solved by qxforever, nikkukun and Potassium
有毒，全场都在卡这个题，还是在国际大师 fwq 的调试下才过掉。
最开始的做法是，先处理出每个数对应的所有给定质数的倍数，然后对每个 $i$ 维护一个质数 $map$，从左到右能够转移的位置是递增的，但显然复杂度两个 $\log$ 不太行，于是把 $map$ 换成数组，变成了一个 $\log$，但还是过不了。然后就卡在这里了，因为认为前面处理倍数也有一个 $\log$，所以就认为是卡常。
可是被忽略的一点是， $|P|\log n$ 和 $n\log n$ 差一个 $10$ 倍大常数…于是对于每个转移的位置进行一下整个区间的扩展，扩展的时候就变成了线性。而质因子倍数个数是 $\log \log n$，因此总复杂度实际是 $O(n+n\log\log n)$ 的。
AC代码 - by qxforever and Potassium
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
typedef long long ll;
using namespace std;
void _debug() {
std::cerr << std::endl;
}
template <typename T, typename... U> void _debug(T t, U... args) {
std::cerr << " " << t;
_debug(args...);
}
int p[N];
unsigned long long ans[N];
int isnp[N], cnt, pri[N];
int q[N], hd, tl;
void sieve() {
int i, j;
isnp[0] = isnp[1] = 1;
for (i = 2; i < N; i++) {
if (!isnp[i]) pri[cnt++] = i;
for (j = 0; j < cnt; j++) {
if (i * pri[j] >= N) break;
isnp[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
}
}
}
int main() {
// sieve();
int i, j, T, n, s;
scanf("%d", &T);
// T=15;
while (T--) {
int flag = 0, _n;
// n=2000000;s=100000;
scanf("%d%d", &n, &s); //_n=n;
ll prod = 1;
int mxp = 0;
for (i = 0; i < s; i++) {
scanf("%d", &p[i]);
// p[i] = pri[i];
mxp = max(mxp, p[i]);
}
for (int i = 0; i <= n; i++) ans[i] = 0;
// sort(p, p + s);
vector<int> mx(n + 1);
for (i = 0; i < s; i++) {
for (j = p[i]; j <= n; j += p[i]) {
// v[j].pb(i);
mx[j] = max(mx[j], p[i]);
}
}
// for (int i = 0; i < n; i++) debug(i, mx[i]);
ans[1] = 1;
int L = 1, R = mxp - 1, v = 1;
while (L <= n) {
int upp = min(n, R);
int nxt = 0;
for (int i = L; i <= upp; i++) {
ans[i] = v;
nxt = max(nxt, i + mx[i] - 1);
}
if (nxt == 0) break;
L = R + 1, R = nxt;
debug(L, R);
v++;
}
unsigned long long res = 0, bas = 1;
for (i = n; i >= 1; i--) {
res += ans[i] * bas;
bas = bas * 23333;
// debug(i, ans[i]);
}
printf("%llu\n", res);
// cout << 1.0 * clock() / CLOCKS_PER_SEC << '\n';
}
return 0;
}
M
题目描述
解题思路
AC代码
2