0%

T1 变换

题意

求有多少个长度为$n$的序列$a_i$,满足$a_i$在$1$到$2^k-1$之间,并且它的前缀或序列单调递增。

阅读全文 »

T1 环游

题意

给出一张$n$个点$m$条边的无向图和三个点$a,b,c$。你要找到一条从$a$出发,依次经过$b$和$c$,最后回到$a$的路径,使得除了$a$被经过两次以外,其它所有点至多只被经过一次。保证$a,c$之间存在三条点不相交的路径。输出方案。

阅读全文 »

A 幸运日

题意

定义一个递推数列:

其中$A,B,X,Y,Z,P,C$都是输入的常量。保证$P$是质数。

$Q$次询问,每次询问给出一个区间$[l_i,r_i]$,询问区间内有多少个数字$k$满足$f_k=C$。

时间限制$0.5s$。

题解

由于递推是在模意义下进行的,因此我们可以断言循环节一定不超过$P^2$,因为某两个位置如果它们的前两项相同,那么这两个位置也一定相同。根据抽屉原理周期一定不超过$P^2$。

$f$的转移可以看作一个$3$阶矩阵,不妨设这个矩阵为$A$。

假设初始矩阵$S=[B,A,1]$,那么有

此时对于$f_i$与$f_{i-1}$构成的矩阵$S’=[f_i,f_{i-1},1]$,有$S’=S\times A^{i-2}$。

接下来我们尝试求出$f$的周期。这等价于我们要找到方程

的最小正整数解$x$。

注意,如果$S=[B,A,1]$不满秩,即$\det S=0$,那么$S$的逆不存在,此时我们不能将等式两边同时除以$S$。

解决方法是保留$S$,用类似BSGS的方法,将$x$拆成$im-j$,等式变为

取$m=P$,由于最小周期的长度不超过$P^2$,因此它一定可以被表示为$im-j$的形式,这里$i,j$的大小都不超过$m$。

接下来我们枚举$f_k=C$时的$f_{k-1}$,如果$f_{k-1}$是一个定值$y$,那么这样的$(y,C)$对在一个周期里面至多只会出现一次。因此,等价于我们要判断是否存在一个$x$,满足

沿用之前的方法,将$x$拆为$im-j$的形式。注意到插入的$SA^{im}$的个数为$\frac{P^2}{m}$,枚举$j$的复杂度为$m$。由于$y$有$P$种取值,为了平衡复杂度,我们可以取$m=\sqrt P$,或者干脆周期的$\frac{1}{4}$次方,此时如果使用手写哈希表,就可以做到$O(P\sqrt P)$的复杂度。

需要注意的是,如果$Y=0$,此时$A$不是满秩的,可能不存在$x$使得$SA^x=S$,此时$f_i$只与$f_{i-1}$有关,因此循环节长度不超过$P$,我们可以令$f_3$为循环的开头,暴力寻找循环节即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<unsigned int, int> P;

int mod;

const int SZ = 32768;

struct HashMap {
vector<P> buff[SZ];

void insert(unsigned int x, int y) {
int t = x % SZ;
buff[t].push_back(P(x, y));
}

int query(unsigned int x) {
int t = x % SZ;
for (auto v : buff[t]) if (v.first == x) return v.second;
return -1;
}

void clear() {
for (int i = 0; i < SZ; i++) buff[i].clear();
}
} T1;

struct Matrix {
int a[3][3];
int* operator [] (int x) { return a[x]; }
Matrix() { memset(a, 0, sizeof(a)); }

Matrix operator * (Matrix &b) {
Matrix res;
for (int i = 0; i < 3; i++)
for (int k = 0; k < 3; k++) if (a[i][k])
for (int j = 0; j < 3; j++)
res[i][j] += a[i][k] * b[k][j];
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
res[i][j] %= mod;
return res;
}

unsigned int get() {
unsigned int res = 0;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
res = res * 10007 + a[i][j];
return res;
}
} E;

int period(Matrix x) {
HashMap mp;
Matrix tmp = E;
for (int i = 1; i <= mod; i++)
mp.insert(tmp.get(), i - 1), tmp = tmp * x;
Matrix nw = tmp;
for (int i = 1; i <= mod; i++) {
int res = mp.query(nw.get());
if (res != -1) return i * mod - res;
nw = nw * tmp;
}
assert(0);
}

Matrix Pow(Matrix x, int y) {
Matrix res = E;
for (; y; y >>= 1, x = x * x) if (y & 1) res = res * x;
return res;
}

void solveY0(int A, int B, int X, int Z, int C, int Q) {
int p = 1, t = (B * X + Z) % mod;
vector<int> wkr;
if (t == C) wkr.push_back(1);
for (int i = 2, tA = t; ; i++) {
tA = (tA * X + Z) % mod;
if (tA == t) { p = i - 1; break; }
if (tA == C) wkr.push_back(i);
}
auto calc = [&](LL r) {
if (r <= 0) return 0ll;
LL res = 0;
if (A == C) res++;
if (B == C && r >= 2) res++;
if (r > 2) {
res += wkr.size() * ((r - 2) / p);
res += upper_bound(wkr.begin(), wkr.end(), (r - 2) % p) - wkr.begin();
}
return res;
};
while (Q--) {
LL l, r; scanf("%lld%lld", &l, &r);
printf("%lld\n", calc(r) - calc(l - 1));
}
}

int main() {
int T; scanf("%d", &T), E[0][0] = E[1][1] = E[2][2] = 1;
while (T--) {
T1.clear();
int A, B, X, Y, Z, C, Q;
scanf("%d%d%d%d%d%d%d%d", &A, &B, &X, &Y, &Z, &mod, &C, &Q);
if (Y == 0) { solveY0(A, B, X, Z, C, Q); continue; }
Matrix base, st;
st[0][0] = B, st[0][1] = A, st[0][2] = 1;
base[0][0] = X, base[1][0] = Y, base[2][0] = Z, base[0][1] = base[2][2] = 1;
auto check = [&](int t) {
Matrix zzh = Pow(base, t);
Matrix tp = st * zzh;
return tp.get() == st.get();
};
int p = period(base), tp = p;
for (int i = 1; i * i <= p; i++) if (p % i == 0) {
if (check(i)) tp = min(tp, i);
if (check(p / i)) tp = min(tp, p / i);
}
p = tp;
int limA = pow(p, 0.25), limB = p / limA + 1;
Matrix tmp = Pow(base, limA), nw = st * tmp;
for (int i = 1; i <= limB; i++)
T1.insert(nw.get(), i * limA), nw = nw * tmp;
vector<int> wkr;
for (int i = 0; i < mod; i++) {
Matrix t; t[0][0] = C, t[0][1] = i, t[0][2] = 1, t = t * base;
for (int j = 1; j <= limA; j++) {
int ans = T1.query(t.get());
if (ans != -1) { wkr.push_back((ans - j + 1) % p + 1); break; }
t = t * base;
}
}
sort(wkr.begin(), wkr.end());
auto calc = [&](LL r) {
if (r <= 0) return 0ll;
LL res = wkr.size() * (r / p);
res += upper_bound(wkr.begin(), wkr.end(), r % p) - wkr.begin();
return res;
};
while (Q--) {
LL l, r; scanf("%lld%lld", &l, &r);
printf("%lld\n", calc(r) - calc(l - 1));
}
}
}

B 字母树上

题意

维护两个字符串的集合$S,T$,最初,每个集合都包含一个编号为$1$的空串。要求支持以下操作:

  1. 将字符$c$加入到字符串$S_i$的末尾得到一个新的字符串,将这个字符串加入到$S$。
  2. 将字符$c$加入到字符串$T_i$的开头或结尾得到一个新的字符串,将这个字符串加入到$T$。
  3. 选择$T$中的两个字符串$T_i,T_j$,将这两个字符串拼起来得到$T_iT_j$,将这个新的字符串加入到$T$。
  4. 询问$T_i$在$S_j$中的出现次数。

题解

将$S,T$中的所有串全部反过来,此时$1$操作就变成了向前添加字符,$2,3$操作本质不变。为啥要这样整之后会说。

我们不妨将此时倒过来的$S,T$串全部称为“正的”。

将所有$S$串倒着插入一棵trie树中,我们有以下几点共识:

  • 两个串$a,b$在trie上的$lca$是它们的最长公共后缀。
  • 每次操作$1$相当于在trie上接一个叶子出来。
  • trie上的一个点代表的串为这个点到根每次走父亲所连成的字符串。

接着我们尝试建出所有$S$串的后缀数组,即将$S$串以及它们的所有后缀拿出来排序。容易发现串的总数为trie的节点数量,这个数量是$O(n)$级别的。

考虑给你一个字符串$A$,如何不用SA建出它的后缀数组。

建出$A$反串的后缀自动机,此时parent树就是一棵后缀树,我们就可以直接通过比较dfs序来比较两个后缀的大小。

而此时所有$S$的反串恰好就是从trie的根节点开始走,走到每个点所代表的串,最开始将$S,T$倒过来的意义就在于此。

因此我们直接将这棵trie当作正的,然后建出它的广义后缀自动机,在parent树上定位trie上的每个节点,接着将所有节点按照dfs序排序就得到了后缀数组。

接下来后缀自动机就没用了,我们只会用到这棵trie以及后缀数组。

对于$T$中的一个串$T_i$来说,如果它不是trie上任何一个串的子串,那么它以及所有由它得到的串都不可能是$S$的子串。

否则,我们一定可以通过一个区间$[l,r]$来表示这个串,它表示$T_i$是后缀数组上排名为$[l,r]$的串的前缀。这个区间是极长的。

$2$操作的本质与$3$操作相同,接下来我们只讨论$3$操作。

假设我们现在要将两个串$T_i,T_j$拼接成$T_iT_j$,它们构成的区间分别为$[l_i,r_i],[l_j,r_j]$。合并后的区间为$[l’,r’]$。

显然,$T_i$是$T_iT_j$的前缀,这意味着$[l’,r’]\subset [l_i,r_i]$。

这等价于我们要在$[l_i,r_i]$中找到一个极长的区间$[l’,r’]$,使得排名为$l’-1$的串以及排名为$r’+1$的串都不以$T_iT_j$为前缀,相当于要比较这两个串去掉长度为$|T_i|$的前缀之后与$T_j$的大小关系。

而“去掉长度为$|T_i|$的前缀”就相当于在trie上找到这个点的第$|T_i|$级祖先,这个可以通过长链剖分加速。

接着我们就可以直接通过比较后缀排名得到两个串的大小关系,二分即可找到$[l’,r’]$。

代码就咕了。

C 1.99

题意

平面上有$n$个点,还有一个常数$D$,满足任意两点的距离要么$\leq D$,要么$\geq 1.99D$。

现在求有多少个点的子集,满足子集内任意两点的距离都$\geq 1.99D$,对$10^9+7$取模。

题解

画一下图可以发现,如果我们将$\leq D$的点连起来,那么最终这张图一定是长成这样的:

image-20210115101136907

大点内部所有小点连成了一个完全图,两个大点之间的连边表示所有小点之间都互相有连边。

如果我们只看大点的话,一个连通块要么是一条链,要么是一个环,没有任何其它情况。

我们可以将整个连通块拿出来单独做一遍$dp$,问题转化为给你一个序列或者环$a_i$,不能选择相邻的位置,第$i$个位置有$a_i$种选法的方案数。

关于如何找到一个大点内的所有小点,我们可以对每个点整一个bitset,存一下与它相连的所有点。如果$i,j$不相连,那么它们的bitset的交一定构成了一个大点。

最后需要注意的是对于每个连通块我们应该优先找度数为$1$的点,如果找不到的话再找其它点。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int mod = 1e9 + 7;

typedef long long LL;

bitset<N> p[N], c[N];

bool isRT[N], vis[N];

int dp[2][2][N];

int solve(vector<int> v, int type) {
int n = v.size();
for (int t = 0; t < 4; t++)
for (int i = 1; i <= n; i++) dp[t & 1][t >> 1][i] = 0;
dp[1][1][1] = v[0], dp[0][0][1] = 1;
for (int i = 2; i <= n; i++) {
for (int a = 0; a <= 1; a++)
for (int b = 0; b <= 1; b++) if (dp[a][b][i - 1]) {
if (!b) dp[a][1][i] = (dp[a][1][i] + (LL)dp[a][b][i - 1] * v[i - 1]) % mod;
dp[a][0][i] = (dp[a][0][i] + dp[a][b][i - 1]) % mod;
}
}
// cout << type << endl;
if (!type) return ((LL)dp[0][1][n] + dp[1][0][n] + dp[1][1][n] + dp[0][0][n]) % mod;
return ((LL)dp[0][1][n] + dp[1][0][n] + dp[0][0][n]) % mod;
}

vector<int> G[N]; int ind[N];

struct OnePointNineNine {
int countSubsets(vector<int> x, vector<int> y, int D) {
int n = x.size();
auto check = [&](int a, int b) { // 1-base
a--, b--;
return (LL)(x[a] - x[b]) * (x[a] - x[b]) +
(LL)(y[a] - y[b]) * (y[a] - y[b]) <= (LL)D * D;
};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) if (check(i, j)) p[i][j] = 1;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++) if (!check(i, j)) {
bitset<N> res = p[i] & p[j];
if (!res.any()) continue;
p[i] ^= res, p[j] ^= res;
int u = res._Find_first();
if (!c[u].any()) c[u] = res;
}
for (int i = 1; i <= n; i++) if (!vis[i]) {
isRT[i] = 1;
if (!c[i].any()) c[i] = p[i];
for (int j = 1; j <= n; j++) if (c[i][j]) vis[j] = 1;
}
memset(vis, 0, sizeof(vis));
int res = 1;
for (int i = 1; i <= n; i++) if (isRT[i]) {
for (int j = 1; j <= n; j++) if (j != i && isRT[j] && check(i, j)) {
G[i].push_back(j), ind[i]++;
}
}
auto push = [&](int i) {
int nw = i, ls = 0, flag = 0;
vector<int> tmp = { (int)c[i].count() };
while (233) {
vis[nw] = 1; int nxt = 0;
for (auto v : G[nw]) if (v != ls) {
if (vis[v]) { flag = 1; break; }
tmp.push_back(c[v].count()), nxt = v; break;
}
if (nxt) ls = nw, nw = nxt;
else break;
}
res = (LL)res * solve(tmp, flag) % mod;
};
for (int i = 1; i <= n; i++)
if (isRT[i] && ind[i] <= 1 && !vis[i]) push(i);
for (int i = 1; i <= n; i++)
if (isRT[i] && !vis[i]) push(i);
return res;
}
};

A EnclosingTriangle

题意

一个$m\times m$的网格,边界上是红点,内部有$n$个黑点。你需要求出有多少个以红点为顶点的三角形,满足这个三角形包含了所有的黑点。

df

阅读全文 »

A PublicTransitHard

题意

给一棵树,树上有两个可以重合的传送点$i,j$,每条边长度为$1$。定义$a,b$的距离为从$a$走到$b$的最短距离,当在$i$号点时可以选择是否传送到$j$号点,且不消耗时间。给定$k$,求出满足任意两点的距离都不超过$k$的选择传送点的方案数。

阅读全文 »

T1 队伍分配

给出一张有向图,你需要将所有点分为两个非空的集合,使得两个集合内部任意两个点之间都有边相连,同时最小化两个集合大小之差的绝对值。

阅读全文 »

T1 小鸣的疑惑

给出一个长度为$n$的数列,每次会随机选择一对相邻的数,然后将这对相邻的数变为左边的数减去右边的数。操作$n-1$次直到只剩下最后一个数,问这个数的期望。

阅读全文 »

题意

给定$n$,你需要将$n$划分为若干个正整数,且每个数仅能包含质因子$2$和$3$,使得任意两个划分出的数都不为倍数关系。多组数据,输出方案。

阅读全文 »

题意

有$n$个$01$变量,你需要构造若干个条件$a\rightarrow b$,表示如果$a$成立那么$b$也成立,这里$a,b$可以为某个变量或者这个变量的值取反(即$a$或$!a$)。

给出三种所有变量的取值,你需要构造一些条件使得这三种取值是唯三满足条件的方案。约束总数不能超过$500$。

阅读全文 »