CF#536Div2の题解(E&F)

$0x01~~Preface$

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

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

简单总结一下前面四道题$\color{red}{Link}$

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

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

  • C题:sb题,一个贪心(其实是数学上可proof的数学题但被我当贪心题做了XD),大概就是你胡乱排个序之后胡搞一下就好。
  • D题:水题,思考一下可得,我们只需要写一个BFS+一个优先队列即可,因为无向图+随便走=胡搞八搞

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

$0x02~~E\cdot \text{Lunar New Year and Red Envelopes}$

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

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

$\mathfrak {Solution}$

呃,其实比较容易的发现就是个时间线$DP$。根据”$n$不大就DP$n$”的是指导思想(瞎扯的),我们应该按时间$DP$。那么第一步就是把每个区间的信息映射到时间线上去。这个时候有一个比较妙的$idea$。首先我们给每个区间的$s$和$e+1$在时间线上分别打上不同的标记,之后我们考虑沿时间线从前向后扫描每一段区间,每当遇到一个区间的$s$时就丢到一个$multiset$里面,反之遇到$e+1$时就$erase$。然后这样我们只顺便乱搞一下就可以得出每个时间点最优的方案。

之后?之后就直接$nm$的DP啊,毕竟$nm$只有$20million$那么大。

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

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
#include <map>
#include <vector>
#include <cstdio>
#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 << endl ; return 0 ;
}

$0x03~~F\cdot \text{Lunar New Year and a Recursive Sequence}$

$Link$

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

$\mathfrak {Solution}$

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

首先我们观察一般形式:$$F_x = \begin{cases}1~, &\rm{x<k} \newline ?~, & \rm{x = k} \newline \prod\limits_{j=1}^kF_{x-j}^{b_j} , & \rm{x>k}\end{cases}~ (\mod 998,244,353)$$

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

次我们选择$998,244,353​$的原根作为底数。因为原根有一个很优美的性质,就是$p​$的原根的幂次可以遍历$p​$的简化剩余系。而由$NTT​$里得到的经验,这个模数的最小原根是$3​$。


原根的基本定义:设$g$为$p$的一个原根,则满足:
$$𝑔^{𝑝−1} \equiv 1(\mod p)$$
$$∀1≤𝑘<𝑝−1, 𝑔^𝑘 \not \equiv 1(\mod p)$$


之后呢?之后我们就找一个函数$q(x)$,令$$g^{q(x)} \equiv x(\bmod p)$$ 目的是为了构造一个$l_x = q(F_x)$,使得等式$$g^{l_x} \equiv \prod \limits_{i=1}^{k}g^{b_il_{x-i}}( \mod p)$$成立。而比较特殊的是,因为$F_1$~$F_{k-1}$都为$1$,所以$l_i=0\quad(1 \leq i <k)$ 。那么也就是说对于指数上的$l_x$满足$$l_x \equiv \sum\limits_{i=1}^{k}b_il_{x-i}( \mod p-1)$$这就是一个线性递推的形式了。

此处有个小$trick$,就是我们为了防止$l_x$过大,我们需要对它取模,此时直接依据费马小定理,取$p-1$做模数即可。

接下来是一个十分巧妙的$Idea$,我们虽然不知道$l_k$,但是我们可以知道$l_k$到$l_n$是如何变化的。观察题目性质,$$l_j = \omega_j l_k \mod(p-1)$$其中的$\omega_j$是一个关于$b_k$的常量因子。证明也比较简单,因为$l_i=0\quad(1 \leq i < k) $是显然的。

那么我们只需要做一下矩阵快速幂——幂次上是$n-k$——就可以得出$\omega_n$来。而我们的$l_n$是可以通过对原根$g$求$BSGS$解得的。那么现在就是$$l_k\omega_n = l_n \mod (p-1)$$移个项可以得到$$l_k \omega_n + t(p-1)= l_n$$由于原题让求的是最小的正整数解,所以应用一下$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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>

#define MAXN 108
#define LL long long
#define Mod 998244353

using namespace std ;

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 ;
}
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)
Ans.M[i][j] = (A.M[i][j] + B.M[i][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)), 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 ;
}

$0x00\quad$后记

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

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

完了,要跪了。

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

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

-------------本文结束感谢您的阅读-------------