【训练记录】6.12 训练笔记

日常营业.png

今天心血来潮打了两场。这些东西总算是告一段落了233

A.M.

A

设 $f_i$ 为斐波那切数列第 $i$ 项。已知

求 $\sum g_i$ .

$1\leq n\leq 10^{18}$ 。

$O(n)$ 的暴力是比较简单的,只需要考虑对每个 $f_i$ ,会有 $f_1,f_2\cdots f_{n-i}$ 这些数与之相乘产生贡献。这样就可以用一个前缀和来线性算。

然后满分做法当然就是要推式子。考虑用 $f_i=f_{i-1}+f_{i-2}$ 进行展开可得:

于是就可以直接矩阵快速幂了。

B


$1 \leq n \leq 10^{5}, 0 \leq l_{i} \leq r_{i}<2^{31}$。

学 FWT 的时候记住的一个推论:

${\rm count}$ 是二进制下 $1$ 的个数。这个不难证。那么问题就可以转化成快速维护区间中 ${\rm count}$ 为奇数和偶数的个数。关于这个有两种不同的做法:

Sol 1

考虑直接用 set 维护区间,每次新加进来对非交集部分进行数位 DP。复杂度 $O(n\log V)$ 。

Sol 2

是别人比较神奇的做法。考虑直接维护一棵动态开点线段树来维护区间信息。然后考虑一个性质,大概是说发现线段树在拆区间的时候是二进制拆法,对于 $len=1$ 的区间可以直接算,$len>1$ 的区间必然是长度为 $2^p$ 的连续段,而这个连续段中可以知道 ${\rm count}$ 为奇数和偶数的分别占一半一半。于是就就可以比较简单地维护出来。

C

$2 \leq n \leq 10^{5}, 1 \leq q \leq 10^{5},\sum k\leq 2\times 10^5$ .

比较考察基本功的题目。首先可以知道,设一个字符串里 $0$ 最后出现的位置为 $A$,$1$ 最后出现的位置为 $B$,那么这个字符串出现的概率就是 $2^{-\min(A,B)}$ 。之后考虑对每组询问,通过枚举+分类讨论 $s=\min(A,B)$ 来解决。以下默认当作 $a_1,a_2\cdots a_k$ 这些位置都变成 $0$ :

1、$s=a_k,s\neq n$ 。这样相当于计算剩下的位置在什么地方出现,所以答案为 $\dbinom{s-k}{n-k}\times 2^{-s}$ 。

2、$s=B,a_i\lt s\lt a_{i+1}$ 。这样相当于拿掉了一个 $1$ ,于是方案数为 $\dbinom{s-1-i}{n-i}$ 。这部分可以考虑对所有这样的 $s$ 做一个前缀和,询问的时候就可以 $O(k)$ 计算了。

3、$s>a_k,s=A$ 。这样相当于拿掉了一个 $0$ ,方案数就是 $\dbinom{s-k-1}{n-k-1}$ 。注意到这是对不同的 $k$ 都需要预处理处一个前缀和,看上去复杂度很爆炸。但是考虑 $\sum k\leq 2\times 10^5$ ,也就是本质不同的 $k$ 只会有至多 $O(\sqrt {2e5})$ 的样子。于是可以离线下来做。

于是最后复杂度 $O\left(\sum k+n\sqrt n\right)$ ,可以通过本题。

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
#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

#define fr first
#define sc second
#define il inline

using namespace std ;

typedef long long ll ;

const int N = 400050 ;

const int P = 998244353 ;

const ll I2 = 499122177 ;

ll ans[N] ;
ll fac[N] = {1} ;
ll inv[N] = {1} ;
ll pwi2[N] = {1} ;
ll s[N] ; // \sum \binom{n-1}{i}\times \dfrac{1}{2^{j}}

vector < pair<int, int> > qs[N] ;

template <typename T>
void debug(T x, char c = '\n'){ cerr << x << c ; }

template <typename T>
void debug(T *const tp, int minn, int maxn, char v = ' ', char c = '\n'){
for (int i = minn ; i <= maxn ; ++ i) debug(tp[i], v) ; cerr << c ;
}

int arr[N] ;
int n, bin ;
int q, k, m ;

template <typename T>
il void add(T &x, ll y, int mod = P){
x += y ; x = x >= mod ? x - mod : x ;
}
template <typename T>
il void dec(T &x, ll y, int mod = P){
x -= y ; x = x < 0 ? x + mod : x ;
}
template <typename T>
il T addn(T x, ll y, int mod = P){
x += y ; return (x = x > mod ? x - mod : x) ;
}
template <typename T>
il T decn(T x, ll y, int mod = P){
x -= y ; return (x = x < 0 ? x + mod : x) ;
}

il ll expow(ll x, ll y, ll mod = P){
ll res = 1 ;
while (y){
if (y & 1)
res = res * x % mod ;
x = x * x % mod ; y >>= 1 ;
}
return res ;
}

il ll sum(int t){ return t < m ? 0 : s[t] ; }
il ll comb(int x, int y) { return fac[x] * inv[y] % P * inv[x - y] % P ; }
void pre_do(){
bin = n << 1 ;
for (int i = 1 ; i <= bin ; ++ i)
fac[i] = fac[i - 1] * i % P ;
inv[bin] = expow(fac[bin], P - 2, P) ;
for (int i = bin ; i >= 1 ; -- i)
inv[i - 1] = inv[i] * i % P ;
for (int i = 1 ; i <= bin ; ++ i)
pwi2[i] = pwi2[i - 1] * I2 % P ;
}
void solve(int x){
m = x ; s[x] = pwi2[x] ;
for (int i = x + 1 ; i <= bin ; ++ i)
s[i] = (s[i - 1] + pwi2[i] * comb(i, x) % P) % P ;
// debug(s, 1, n << 1) ;
}

int main(){
cin >> n >> q ;
pre_do() ; solve(n - 1) ;
// debug(fac, 1, n << 1) ;
// debug(inv, 1, n << 1) ;
// debug(pwi2, 1, n << 1) ;
for (int o = 1 ; o <= q ; ++ o){
scanf("%d", &k) ; arr[k + 1] = bin ;
for (int i = 1 ; i <= k ; ++ i) scanf("%d", &arr[i]) ;
qs[k].push_back(make_pair(o, arr[k])) ;
for (int i = k ; i >= 0 ; -- i){
if (arr[i] != bin){
// cout << arr[i + 1] - (i + 1) - 1 << " " << arr[i] - i - 1 << '\n' ;
add(ans[o], pwi2[i + 1] * decn(sum(arr[i + 1] - (i + 1) - 1), sum(arr[i] - i - 1)) % P) ;
if (arr[i + 1] - (i + 1) - 1 < n - 1) break ;
}
}
if (arr[k] < bin)
add(ans[o], pwi2[arr[k]] * comb(arr[k] - k, n - k) % P) ;
}
// cout << ans[1] << '\n' ;
for (int i = 1 ; i < n ; ++ i){
if (!qs[i].size()) continue ; else solve(n - i - 1) ;
for (auto t : qs[i]){
int x = t.fr, y = t.sc ; if (x == bin) continue ;
add(ans[x], pwi2[i + 1] * decn(sum(bin - (i + 1) - 1), sum(y - i - 1))) ;
}
}
for (int i = 1 ; i <= q ; ++ i)
printf("%lld\n", (ans[i] << 1) % P) ;
return 0 ;
}

/*
15 1
15 1 4 6 10 13 14 15 19 20 21 22 25 26 29 30
*/

P.M.

A

$n \leq 1000000 \leq|x_1|,|y_1|,|x_2|,|y_2| \leq 10^{9}$ 。

比较有趣的结论题?那么就是有个结论:答案绝对不会超过 $3$ 。

大概是考虑由于没有三直线共点,所以每个点 $o$ 必然只被两条直线经过,相邻点的个数不会超过 $4$。 可以将交点按x、y坐标排序。不难发现在考虑到 $o$ 时,它有恰好两个位于不同直线上的相邻的点被赋了颜色,这时使用没用过的颜色即可。

然后考虑如果只有一个交点,那么色数为 $1$ 。否则考虑如果全部的直线只有两种斜率,那么色数为 $2$ ,因为此时必然不会形成三角形。

B

$1\leq n\leq 1000,a_i,b_i\leq 10^5$ 。

暴力是可以拼一下的。大概就是说可以用 $2^n$ 做前 $25$ 分,然后暴力 dp,即设 $f_{i,p,q}$ 表示那两个式子的值分别为 $p,q$ 时的最小值,就可以拿到 $50$ pts。

然后考虑还有一档 $c_i=0$ 的部分分。发现这一档部分分本质上就是判断是否可以找出一种合法的方案使得满足那两个式子。那么就可以直接设 $f_{i,v}$ 表示考虑了前 $i$ 个 $x$ ,第一个式子的值为 $v$ 时第二个式子的最大值。不难知道这样是 $O(nP)$ 的。

然后考虑满分,又到了喜闻乐见的合并状态环节。考虑设 $f_{i,t}$ 表示确定了前 $i$ 个 $x_i$,$\sum_{j<i} a_{j} x_{j} \leq t \leq \sum_{j<i} b_{j} x_{j}$ 时的最小值。这个转移本质是和暴力相同的,但是有比较好的性质:

不难发现后面那一维是可以单调队列优化掉的。于是复杂度降为 $O(nP)$ 。

C

$1 \leq n \leq 10^{9}, 1 \leq m \leq 3 \times 10^{5}$ 。

这道题十分强 and 十分有趣!

自己一开始的想法还是挺可以的,虽然到一半就不会了。大概是说考虑计算当一个序列的 gcd 是 $x$ 的时候,它的 lcm 可以有多少种方案。然后…然后就不会了 (x。

考虑设 $f(d)$ 表示有 $\gcd=d$ 的时候,所有可能的 $\rm lcm$ 之积。但这个并不好求,于是这个地方需要做一步容斥的转化。设 $g(d)$ 表示序列中的全部数字都是 $d$ 的倍数时、所有序列的 $\rm lcm$ 之积。那么不难发现他俩之间有这样的关系:

考虑如果知道了 $\{g\}$ ,那么 $f$ 是很容易在 $O(m\times \tau(m))$ 的时间复杂度里算出来的,即考虑从大到小扫,每次对所有 $d|x$ 的 $g(d)$ 除以当前的 $f(x)$ 。是个比较经典的技巧。

然后考虑如何计算 $g$ 。发现此时每个序列可以被完全映射到一个值域为 $[1,V=\left\lfloor\frac{m}{d}\right\rfloor]$ 的区间上。于是可以计算出全部位于 $[1,V]$ 之间的序列的 $\rm lcm$ 之积 $h(V)$ 后,会有

然后考虑 $h$ 的求法。发现由于答案是乘积形式,所以可以对所有在 $1\sim V$ 之间的素数分别计算贡献。考虑对于一个质数 $p$ 的某一个幂 $p^e$,如果 $\rm lcm$ 至少包含 $p_e$ 的方案数为 $q$ ,那么可以用一个差分、或者是贡献平摊的技巧,使之对答案产生 $p^q$ 的贡献。然后这部分可以用总方案数减去那些所有 $p$ 的幂次都 $e$ 的情况得到。

考虑这么做的复杂度。首先有个毛估估等式

而算上枚举质因数幂就要再多一个 $\log $ ,再算上枚举本质不同的 $V$ 的时间,发现大概是

可以通过本题。

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
#include <cstdio>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std ;

typedef long long ll ;

const int N = 300010 ;

const int P = 998244353 ;

int ans ;
int cnt ;
int n, m ;
int f[N] ;
int g[N] ;
int pr[N] ;
int pval[N] ;
bool chk[N] ;
bool vis[N] ;

vector <int> d_[N] ;

ll expow(ll x, ll y, ll mod = P){
ll res = 1 ;
while (y){
if (y & 1)
res = res * x % mod ;
x = x * x % mod ; y >>= 1 ;
}
return res ;
}
void sieve(int T){
for (int i = 2 ; i <= T ; ++ i){
if (!chk[i]) pr[++ cnt] = i ;
for (int j = 1 ; j <= cnt ; ++ j){
if (pr[j] * i >= N) break ;
chk[i * pr[j]] = 1 ;
if (i % pr[j] == 0) break ;
}
}
for (int i = 1 ; i <= T ; ++ i)
for (int j = 1 ; i * j <= T ; ++ j)
d_[i * j].push_back(i) ;
}
inline int sub(int x, int y){
x -= y ; return x < 0 ? x + P - 1 : x ;
}
int main(){
long long q ;
int p, o, z, rr, po ;
cin >> n >> m ; sieve(m) ;
for (int i = 1 ; i <= m ; ++ i)
pval[i] = expow(i, n, P - 1) ;
for (int t = m, d = 1 ; d <= m ; ++ d, t = m / d){
if (vis[t]) continue ;
vis[t] = 1 ; g[t] = 1 ;
for (int i = 1 ; i <= cnt ; ++ i){
q = p = pr[i] ;
po = t - t / p ;
if (p > t) break ;
o = pval[po], z = pval[t], rr = 0 ;
for (int e = 1 ; e <= 30 ; ++ e){
if (q > t) break ;
rr = (rr + sub(z, o)) % (P - 1) ;
o = pval[po += t / q] ; q *= p ;
o = pval[po -= t / q] ;
}
g[t] = g[t] * expow(p, rr) % P ;
}
}
for (int i = 1 ; i <= m ; ++ i)
f[i] = g[m / i] * expow(i, pval[m / i]) % P ;
for (int i = m ; i >= 1 ; -- i){
int rv = expow(f[i], P - 2) ;
for (auto j : d_[i])
if (i != j)
f[j] = 1ll * f[j] * rv % P ;
}
ans = 1 ;
for (int i = 1 ; i <= m ; ++ i)
ans = 1ll * ans * expow(f[i], i) % P ;
printf("%d\n", ans) ; return 0 ;
}