【赛题整理】CF#536Div2の题解(E&F)

春节前的一场 CNRound~名字很 nice 的说~

⑧说别的啦,新年好那个新年好qwq !

前言

emmm​这次 CF 本身打的很顺畅,但是居然unrated了……咕咕咕咕

这是头一次CF有比赛我全部题目都做了……可喜可贺可喜可贺233

简单总结一下前面四道题 Link

  • A题:sb题,$O(n^2)$ 枚举,但是我 check 的时候太粗心WA了一次身败名裂XD

  • B题:sb题,一个模拟,需要一个可以处理优先级的数据结构(其实就是堆但是我一开始想的是线段树)

  • C题:sb题,一个贪心(其实是数学上可proof的数学题但被我当贪心题做了XD),大概就是你胡乱排个序之后胡搞一下就好。(画外音:现在是来自 0202 年的复盘,其实这题的原理是排序不等式)。
  • D题:水题,思考一下可得,我们只需要写一个BFS+一个优先队列即可,因为无向图+随便走=胡搞八搞。本质上是考察的字典序的贪心本质。

下面两道题就好像不是那么水了qaq

E Lunar New Year and Red Envelopes

给 $k$ 个区间,每个区间一个左端点 $s$ 一个右端点 $e$,同时还有一个蜜汁 · 右端点 $t$。顺着时间线$1\sim n$,可以从 $s_i$ 到 $e_i$ 的时间内获得 $w_i$ 的收益,但同时下次的选择必须在 $t_i$ 之后。

最大化收益的思路下,有 $m$ 次机会让选择者在某个时间点啥都不干。求最小的收益。

呃,其实比较容易的发现就是个时间线 dp 。根据 n 不大就dp n 的是指导思想(瞎扯的),我们应该按时间 $dp$。

那么第一步就是把每个区间的信息映射到时间线上去。这个时候有一个比较妙的 $idea$。首先我们给每个区间的 $s$ 和 $e+1$ 在时间线上分别打上不同的标记,之后我们考虑沿时间线从前向后扫描每一段区间,每当遇到一个区间的 $s$ 时就丢到一个 multiset 里面,反之遇到 e+1 时就 erase。然后这样我们只顺便乱搞一下就可以得出每个时间点最优的方案。

之后?之后就直接$O(nm)$的 dp 啊,毕竟 $nm$ 只有 $2\times 10^6$ 。

Ps: 由于STL中 multiset 一删删一串的zz性质,改用map了。

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
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>

#define MAXM 233

#define MAXN 100010

using namespace std ;

struct time_node{
int mark, d, w ;
bool operator < (const time_node &T) const {
return w > T.w || (w == T.w && d > T.d);
}
} base[MAXN] ;
map <time_node, int> M_set ;
vector<time_node>Time[MAXN] ; long long Ans ;
int N, M, K, A, B, C, D, i, j ; long long dp[MAXN][MAXM] ;

int main(){
cin >> N >> M >> K ;
memset(dp, 63, sizeof(dp)) ;
for (i = 1 ; i <= K ; ++ i){
scanf("%d%d%d%d", &A, &B, &C, &D),
Time[A].push_back((time_node){1, C, D}) ;
Time[B + 1].push_back((time_node){2, C, D}) ;
}
for (i = 1 ; i <= N ; ++ i){
register int tot = Time[i].size() ;
for (j = 0 ; j < tot ; ++ j){
if (Time[i][j].mark == 1) ++ M_set[Time[i][j]] ;
else M_set[Time[i][j]] > 1 ?
M_set[Time[i][j]] -- : M_set.erase(Time[i][j]) ;
}
if (M_set.size())
base[i] = (*M_set.begin()).first ;
else base[i] = (time_node){0, i, 0} ;
}
dp[0][0] = 0 ;
Ans = dp[1][1] ;
for (i = 1 ; i <= N ; ++ i){
for (j = 0 ; j <= M ; ++ j){
j > 0 ? dp[i][j] = min(dp[i - 1][j - 1], dp[i][j]) : 1 ;
dp[base[i].d][j] = min(dp[base[i].d][j], dp[i - 1][j] + base[i].w) ;
}
}
for (i = 0 ; i <= M ; ++ i)
Ans = min(Ans, dp[N][i]) ;
cout << Ans << '\n' ; return 0 ;
}

F Lunar New Year and a Recursive Sequence

给你一个序列 $F$ 的 $k$ 项的递推法则(幂次/积式递推),在认定前 $k-1$ 项都满足 $F_x=1$ 的基础上给定 $F_n$,让你倒推出 $F_k$ 来。

恕我直言…这道题我考场上是不可能会的…(已扑街

首先我们观察一般形式:

大体上这个式子是没法做的,因为毕竟是乘积+幂次方递推的形式。但是这个地方有个我没想出来、想出来也不会用的 Idea​,就是我们既然要把乘积转化成求和的形式,那就只能在指数上乱搞。换句话说,我们可以考虑把它的每一项都写成同一个数的幂次,那么递推的时候只需要做加法就可以了。

我们选择 $998,244,353$ 的原根作为底数。因为原根有一个很优美的性质,就是 $p$ 的原根的幂次可以遍历 $p$ 的简化剩余系

而由 NTT 得到的经验可知,这个模数的最小原根是 3。


原根的基本定义:设 $g$ 为 $p$ 的一个原根,则满足:


由于原根的优秀性质,所以可以将这个式子转化成如下形式:

此处是因为 $998244353$ 是一个质数,所以任何 $F$ 在 $\bmod 998244353$ 的意义下都可以被其原根的幂次表示出来。

同时由于指数上的 $l_x$ 满足

这就是一个线性递推的形式了,根据扩展欧拉定理可知应该对 $p-1$ 取模 。

另一方面, $l_n$ 是可以通过解

得到。这就是一个离散对数的形式。用 BSGS 求解即可。

那么在知道 $l_n$ 之后,虽然很难知道 $l_k$,但由于递推方式一致,很容易通过矩乘得到 $l_k\to l_n$ 是怎么变化的。同时观察题目性质可知

其中的 $\pi_n$ 是一个关于 $n$ 的常量因子。因为 $F_1,F_2,F_3\cdots,F_{k-1}$ 都为 $1$,所以 $l_i=0~(1 \leq i <k)$ ,所以之后的项也只会跟 $l_k$ 有关。

那么现在就是

移个项可以得到

由于原题让求的是最小的正整数解,所以用一下 $exgcd$ 判一下是否有解就解决了。

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
map<LL, LL> Hash ;
int N, T, base[MAXN] ;
LL Ft, Hn, Xs, Ans, X, Y, G ;

struct Matrix{
LL M[MAXN][MAXN] ;
void clear() { memset(M, 0, sizeof(M)) ;}
void reset() {
clear() ;
for (int i = 1 ; i <= N ; ++ i) M[i][i] = 1 ;
}
Matrix friend operator *(const Matrix&A, const Matrix &B){
Matrix Ans ; Ans.clear() ;
for (int i = 1 ; i <= N; ++ i)
for (int j = 1 ; j <= N ; ++ j)
for (int k = 1 ; k <= N; ++ k)
Ans.M[i][j] = (Ans.M[i][j] + A.M[i][k] * B.M[k][j]) % (Mod - 1) ;
return Ans ;
}
} ;

inline Matrix expow(Matrix T, LL P){
Matrix Ans ; Ans.reset() ;
while (P){
if (P & 1) Ans = Ans * T ;
T = T * T, P >>= 1 ;
}
return Ans ;
}
inline LL expow(LL a, LL b, LL p){
LL res = 1 ;
while (b){
if (b & 1)
(res *= a) %= p ;
(a *= a) %= p, b >>= 1 ;
}
return res % p ;
}
inline LL bsgs(LL x, LL y, LL p){
LL P = ceil(sqrt(p - 1)) ;
LL Q = expow(x, -P + 2 *(p - 1), p) ;
for (LL i = 1, j = 0 ; j <= P ; ++ j, (i *= x) %= p)
if (!Hash.count(i)) Hash[i] = j ;
for (LL i = y, j = 0 ; j <= P ; ++ j, (i *= Q) %= p)
if (Hash.count(i)) return Hash[i] + j * P ;
}
inline LL exgcd(LL a, LL b, LL &x, LL &y){
if(!b) {x = 1, y = 0 ; return a ;}
LL t = exgcd(b, a % b, y, x) ; y -= a / b * x ; return t ;
}
inline LL qr(){
register LL k = 0, p = 1 ; char c = getchar() ;
while (c < '0' || c > '9') { c = getchar() ; if (c == '-') p = -1 ;}
while (c <= '9' && c >= '0') k = (k << 1) + (k << 3) + c - 48, c = getchar() ;
return k * p ;
}
int main(){
cin >> N ; register int i ;
for (i = 1 ; i <= N ; ++ i) base[i] = qr() ;
cin >> T >> Ft ; Matrix lab ; lab.clear() ;
for (i = 2 ; i <= N ; ++ i) lab.M[i][i - 1] = 1ll ;
for (i = 1 ; i <= N ; ++ i) lab.M[i][N] = 1ll * base[N -i + 1] ;
lab = expow(lab, T - N), Hn = bsgs(3, Ft, Mod), Xs = lab.M[N][N] ;
G = exgcd(Xs, Mod - 1, X, Y) ; if (Hn % G) return puts("-1"), 0 ;
X = (X % (Mod - 1) * (Hn / G) % (Mod - 1) + Mod - 1) % (Mod - 1) ;
Ans = expow(3, X, Mod) ; cout << Ans << endl ; return 0 ;
}

后记

说实话,这是第一次做整套 CF 的题目…确实,千里挑一的题目就是比你谷上随便找几道题做来劲。$A\sim E$ 都还好,但是 F 实在是…看题解都要想半天的那种…尤其是这个解离散方根的东西…

rqy说 F 题是省选一轮的难度——虽然没说是 D几T几,但我感觉他的语气不像是在说一道很难的题……

完了,要跪了。

奥赛文化课两爆炸,省选进队进你ma,指望着将来没学上,还不如收拾好铺盖早回家 。

​ ——(pks《春日绝句》)