题目链接

题目

给定一颗 \(n\) 个点的树。每个点都一个正整数点权 \(Ai\) ,你需要支持以下两种操作: 1、询问点 \(x\) 和点 \(y\) 之间的路径上的所有点(包括点 \(x\) 和点 \(y\) )的点权是否构成一个从 \(1\) 开始的排列(即若这条链长度为 \(len\) ,那么问点权集合是否为 \({1,2,⋯,len}\) )。

2、将 \(Ax\) 修改为 \(y\)

题解

这道题就是把BZOJ4373上树的版本。
判一个排列直接用自然数幂之和或者是异或和 + hash

有个坑点,当然是对我来说。。。 我用的自然溢出,所以不能随便除数的,所以不应该这么算自然数幂之和

1
2
3
ull su1(int x) {return (x + 1ull) * 1ull * x / 2ull;}
ull su2(int x) {return x * 1ull * (ull)(x + 1) * 1ull * (ull)(x + x + 1) / 6;}
ull su3(int x) {return x * 1ull * (ull)(x + 1) * 1ull * x * 1ull * (ull)(x + 1) / 4ull;}
自然溢出相当于\(\%2^{64}\),显然溢出了不能随便除

阅读全文 »

长城之旅

或许是全网第一篇能看的题解 (?)

首先\(\text{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}\)
根据定义可以证明。

关于\(\gcd\)的一个结论。
\(\gcd(k^{2^l}+1,k^{2^r}+1)=(k\& 1)?2:1\ ,r>l\)

分类讨论一下 1. \(k\%2=0\)时,假设\(k^{2^l}+1\)有约数\(d\),即\(k^{2^l}\equiv -1\pmod d\),又\((k^{2^l})^{2^j}=k^{2^{l+j}},j\ge0\),所以\(k^{2^r}\equiv 1\pmod d\)\(k^{2^r}+1\equiv 2\pmod 2\) ,所以\(k^{2^l}+1\)的约数都不是\(k^{2^r}+1\)的约数,当然\(d=2\)需要单独讨论一下,显然\(k^{2^l}+1\)是奇数。 2. \(k\%2=1\)时,唯一区别是\(k^{2^l}+1\)是偶数,\(\gcd=2\)

所以做法就比较显然。
模数是\(2\)的单独处理。

\(k\%p=0\),显然答案是\(1\)

其余情况,假设\(a=k^{2^l}\)
则乘积等于\((a+1)\times (a^{2^1}+1)\times (a^{2^2}+1)\times ... \times (a^{2^{r-l}}+1)\)
因为每个括号要不选前一个,要不选后一个,所以最后答案是\(\sum_{i=0}^{2^{r-l+1}-1}a^i\),这东西显然是个等比数列求和。

注意此时只是算出了所有数乘积,最后如果\(k\)时奇数还得除一个\(2^{r-l}\)

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

typedef long long ll;
ll k, l, r, p;
int -;

ll fpow(ll a, ll b, ll p) {
ll res = 1;
for (; b; b >>= 1, a = a * a % p) if (b & 1) res = res * a % p;
return res;
}

int main() {
for (scanf("%d", &-); -; ---) {
scanf("%lld %lld %lld %lld", &k, &l, &r, &p);
if (p == 2) {
printf("%d\n", (k & 1) ? 0 : 1);
continue;
}
ll res = 0;
if (k % p == 0)
res = 1;
else {
ll a = fpow(k, fpow(2, l, p - 1), p);
if (a != 1) {
res = fpow(a, fpow(2, r - l + 1, p - 1), p);
res = (res - 1 + p) % p;
res = res * fpow((a - 1 + p) % p, p - 2, p) % p;
} else {
res = fpow(2, r - l + 1, p);
}
}
if (k & 1) res = res * fpow(fpow(2, r - l, p), p - 2, p) % p;
printf("%lld\n", res);
}
return 0;
}
阅读全文 »

题目

有Q个查询,对于每一个查询q[i],请计算S(q[i])%m。 拆一下第二个函数 \[S((\lfloor\frac{n}{k}\rfloor-1)*k+i)=S((n-k)-n\%k+i)\]

可以发现这个式子按\(\mod k\)余数分类后,可以用矩阵乘法来做。

以下来自题解

可以先把数据分块,每K个一块,后一块和前一块之间的关系可以用矩阵来表示。

这个矩阵太大了。直接做矩阵乘法肯定会超时。但是这个矩阵有一个特殊性,使得它的乘法有优化的空间。

C是一个常数,先预处理,那么就可以在log(qi)的时候内计算出S(qi)的值了。

阅读全文 »

备忘录 & 任务列表

小技巧

逆元

线性筛\(1-p\)逆元
\(t=\lfloor P /i\rfloor\)\(k=P\%i\)

\(t*i+k\equiv 0 \pmod {P}\)
\(-t*i\equiv k \pmod {P}\)
\(-t*inv[k]\equiv inv[i]\pmod {P}\)
带回\(t,k\)

1
inv[i]=(P-P/i)*inv[P%i]%P

快速幂

\(\mathjaxcal{O}(\sqrt{P})-\mathjaxcal{O}(1)\)快速幂 https://loj.ac/article/1383

任务列表

阅读全文 »

莓在执行任务时,收集到了 n 份岩浆能源, 其中第 i 份的能量值是 wi ,她 决定将它们分成恰好 k 组带回基地,每一组都要有至少 1 份能源。 每一组能源会对运输设备产生负荷值,若该组有 x 份能源,这 x 份能源能 量值之和为 y , 则产生的负荷值为 x × y 。 每种分组方案产生的负荷是每一组能源产生的负荷值总和,莓想知道所有可 能的分组方案产生的负荷之和对 998244353 取模的结果。

每个\(w-i\)贡献是\(\sum w-i\times |S|\)

也就是一个集合里和每个数配对一下就产生一次贡献。

\(w-i\)在所有可能的集合中自己和自己配对\(w-i\times \begin{Bmatrix}n \\ k\end{Bmatrix}\)
枚举和其他点在一个集合\((w-i+w-j)\times \begin{Bmatrix}n-1 \\ k\end{Bmatrix}\)

\(ans=\sum(w-i)(\begin{Bmatrix}n \\ k\end{Bmatrix}+(n-1)\begin{Bmatrix}n-1 \\ k\end{Bmatrix})\)

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
#include <cstdio>
using namespace std;

const int N = 1e6 + 5, MOD = 998244353;
int n, k, sum, fac[N], ifac[N];

int fpow(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = a * 1ll * a % MOD) if (b & 1) res = res * 1ll * a % MOD;
return res;
}
int C(int n, int k) {
if (k > n) return 0;
return fac[n] * 1ll * ifac[k] % MOD * 1ll * ifac[n - k] % MOD;
}
int S(int n, int k) {
int res = 0;
for (int i = 0; i <= k; i++) {
int g = (i & 1) ? -1 : 1;
g = g * 1ll * fpow(k - i, n) % MOD * C(k, i) % MOD;
g = (g + MOD) % MOD;
res = (res + g) % MOD;
}
res = res * 1ll * ifac[k] % MOD;
return res;
}

int main() {
freopen("ichigo.in", "r", stdin);
freopen("ichigo.out", "w", stdout);
scanf("%d %d", &n, &k);
for (int i = 1, x; i <= n; i++) scanf("%d", &x), sum = (sum + x) % MOD;
fac[0] = 1;
for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * 1ll * i % MOD;
ifac[n] = fpow(fac[n], MOD - 2);
for (int i = n - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * 1ll * (i + 1) % MOD;
printf("%lld\n", sum * 1ll * (S(n, k) * 1ll + (n - 1) * 1ll * S(n - 1, k) % MOD) % MOD);
return 0;
}

题目链接

喜提最快解 (?)
## 题目 给定\(n,k\) 求满足\(\gcd(A_{l\cdots r})\cdot(A-l\ \mathjaxrm{xor} \ A_{l+1}\ \mathjaxrm{xor} \cdots \mathjaxrm{xor} \ A-r)=k\)且字典序最小的\(l,r\)

分析

可以看我前两篇博客
按照基本方法,枚举右端点\(r\)
然后我们需要什么呢

每个左端点\(l\)对应的区间\(\gcd\)\(xor\)
对于\(gcd\)的维护看这里

\(A-l\ \mathjaxrm{xor} \ A_{l+1}\ \mathjaxrm{xor} \cdots \mathjaxrm{xor} \ A-r\)这东西显然是做个异或前缀和
因为右端点固定,我们显然求\(sum[r]\oplus sum[l-1] =\frac{k}{\gcd}\)
异或有个好性质\(a\oplus b=c\),则\(a\oplus c=b\)

update:分析没什么问题,代码有点问题,代码删了。 正确做法还是得记录下每个\(xor\)所有的位置,二分一个满足要求的位置更新答案。

题目: UVa1642

solution

因为要求一个最优的子序列,可以想到枚举这个子序列的右端点\(j\)。 那么怎么快速算出左端点\(i\)的答案呢?
枚举每一个左端点,如果能知道这个子序列所有元素的\(gcd\)值就好了。
先考虑这样一个序列\(5,8,8,6,2\),假设现在\(j=4\),可以算出所有子序列对应的\(gcd\)。 1. \(i=1\), \(gcd(a_1,a_2,a_3,a_4)=1\) 2. \(i=2\), \(gcd(a_2,a_3,a_4)=2\) 3. \(i=3\), \(gcd(a_3,a_4)=2\) 4. \(i=4\), \(gcd(a_4)=6\)

注意到不同子序列的\(gcd\)值有可能是相等的,事实上\(gcd\)值的种类最多不会超过\(\log_2 a_j\)个,因为\(a_j\)的约数个数一定不多于\(\log_2 a_j\)
上表从下向上看,每次增加一个元素的时候,\(gcd\)值是不变或者减小的,而且变小时一定会变成\(a_j\)的一个约数。所以就维护每个左端点对应的区间\(gcd\)值(即\(gcd(a[i],a[i+1],...,a[j])\)),增加一个元素(即\(j\) -> \(j+1\))时,更新加上该元素后的区间\(gcd\)值就可以。
知道了当前每个左端点对应的\(gcd\),区间长度也是已知的,就可以计算答案了,对于每个区间的结果取一个最大值。
但是直接这样做复杂度是不对的,\(O(n^2log n)\)显然过不了。那怎么办呢。 我们可以发现,如果两个左端点的\(gcd\)相等,那么\(i\)更小的一定会更优,所以直接把劣的删除,对后面不造成影响。这样一来每次要枚举的\(i\)就和\(gcd\)的个数有关,复杂度是\(O(nlog^2 n)\),可以通过本题。

code

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

typedef long long ll;
const int N = 1e5 + 5;
ll n, a[N];
vector<pair<int, ll> > v;

ll read() {
ll w = 0; char ch = getchar();
while(ch > '9' || ch < '0') ch = getchar();
while(ch >= '0' && ch <= '9') {
w = w * 10 + ch - 48;
ch = getchar();
}
return w;
}
ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a % b);
}

int main() {
ll T = read();
while(T--) {
ll ans = 0; v.clear();
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int j = 1; j <= n; j++) {
v.push_back({j, a[j]});
for(int i = v.size() - 2; i >=0; i--) {
v[i].second = gcd(v[i].second, a[j]);
if(v[i].second == v[i + 1].second) v.erase(v.begin() + i + 1);
}
for(int i = 0; i < v.size(); i++) {
ans = max(ans, (j - v[i].first + 1) * (v[i].second));
}
}
printf("%lld\n", ans);
}
return 0;
}

题目: luogu 签到题IV
话说这道题和UVA1642 魔法GCD很类似 # Solution

题目要求找所有满足条件的子序列,可以考虑固定右端点\(j\),然后快速求出每个左端点\(i\)对应的子序列的有关信息。
好像有点抽象,可以想一下这个序列怎么做。
\[3,4,6,4,2\] \(j=4\)时,我们写一下所有子序列的有关值,即\(gcd(a-i,a_{i+1}...a-j)\)\((a-i\ or\ a_{i+1}...\ or\ a-j)\) 1. \(i=1\)时,\(gcd(a-1,a-2,a-3,a-4)=1\), \((a-1\ or\ a-2\ or\ a-3\ or\ a-4)=7\) 2. \(i=2\)时,\(gcd(a-2,a-3,a-4)=2\), \((a-2\ or\ a-3\ or\ a-4)=6\) 3. \(i=3\)时,\(gcd(a-3,a-4)=2\), \((a-3\ or\ a-4)=6\) 4. \(i=4\)时,\(gcd(a-4)=4\), \((a-4 \ or\ a-4)=4\)

很显然我们可以把每个左端点\(i\)对应的有关信息存下来,然后一个个判断是否符合条件。每次\(j\)右移时(即增加一个元素)都把每个左端点维护的信息更新。这样做是\(O(n^2 logn)\)的。
观察上表,可以发现有的\(gcd\)或者二进制或的和是相等的。事实上每加入一个新的数,序列的\(gcd\)是不变或者变小的,且变小时会变为\(a-j\)的约数。而序列的二进制或则是不变或者变大的,如果把数写成二进制的形式,可以发现如果增大只会在某一位增加\(1\),而一共只有\(\log-2 a-j\)位。所以\(gcd\)或者二进制或的值的个数都是\(log\)级别的。
那么如果把相等的值合并,复杂度可以降为\(O(nlog^2 n)\)的。
因为\(a\oplus b=k\),有\(a\oplus k=b\)。那么可以分别维护\(gcd(a-i,a_{i+1}...a-j)\)\((a-i\ or\ a_{i+1}...\ or\ a-j)\)。计算出每个\(gcd\oplus k\),之后去找有没有等于\(gcd\oplus k\)\(or\)值。
怎么维护呢?可以发现无论是\(gcd\)还是\(or\)的值都是单调的,受到\(ODT\)的启发,可以把相同的值合并为一个块,也就是记录它的左右端点和值,每次查询都\(O(log)\)的算出每个\(gcd\oplus k\)。然后二分查找或者直接枚举有没有与它相等的\(or\)值,如果有,就把两个区间(该\(gcd\)对应的区间和\(or\)对应的区间)取交集,答案累加上此时的元素个数就可以。时间复杂度\(O(n log^2 n)\),实际上很难有每次都使表里有\(\log a-j\)个元素的数据,所以复杂度和\(O(nlog n)\)接近。

不知道为什么二分还没直接枚举跑得快QwQ

Code

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

const int N = 5e5 + 10;
int n, k, a[N];
struct node {
int l, r, v;
};
vector<node> v, o;

int read() {
int w = 0; char ch = getchar();
while(ch > '9' || ch < '0') ch = getchar();
while(ch >= '0' && ch <= '9') {
w = w * 10 + ch - 48;
ch = getchar();
}
return w;
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
node bound(int x) {
for(int i = 0; i < o.size(); i++) {
if(o[i].v == x) return {o[i].l, o[i].r, x};
}
return {0, 0, -1};
}

int main() {
long long sum = 0;
n = read(); k = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int j = 1; j <= n; j++) {
v.push-back({j, j, a[j]});
o.push-back({j, j, a[j]});
for(int i = v.size() - 2; i >= 0; i--) {
v[i].v = gcd(v[i].v, a[j]);
if(v[i].v == v[i + 1].v) {
v[i].r = v[i + 1].r;
v.erase(v.begin() + i + 1);
}
}
for(int i = o.size() - 2; i >= 0; i--) {
o[i].v |= a[j];
if(o[i].v == o[i + 1].v) {
o[i].r = o[i + 1].r;
o.erase(o.begin() + i + 1);
}
}
for(int i = 0; i < v.size(); i++) {
node ans = bound(v[i].v ^ k);
if(ans.v == -1 || ans.l > v[i].r || ans.r < v[i].l) continue;
ans.l = max(v[i].l, ans.l); ans.r = min(ans.r, v[i].r);
sum += ans.r - ans.l + 1;
}
}
printf("%lld\n",sum);
return 0;
}

题目链接

和社论不一样的方法
## 题目
已知\(f(n) = \prod\limits_{d|n} \mu(d)\)\(\sum\limits_{i=1}^n f(i) \bmod 998244353\)\(n\leq 10^{10}\)

分析

\(\sum\limits_{i=1}^n\prod\limits_{d|i} \mu(d)\)
我们来观察一下\(\prod\limits_{d|i} \mu(d)\)有什么特点。

首先如果\(i\)有平方因子,那么它等于\(0\)
\(i\)为素数,等于\(1\)

其他情况,我们考虑有多少个约数\(\mu (d)=-1\)
我们把\(i\)唯一分解一下,一定等于\(\prod p-i^1\)
假设一共有\(cnt\)个素约数,那么\(d\)无非就是从些质约数里面选一些出来。
等于\(\binom{cnt}{1}+\binom{cnt}{3}+...+\binom{cnt}{2k+1}\)
也就是\(\sum_{i=1}^{cnt}\binom{cnt}{i}[i\nmid 2]=2^{cnt-1}\)
所以只有\(cnt=1\)时才为\(-1\)\(cnt>1\)时都等于\(1\),而\(cnt=1\)的情况已经讨论过了。

我们把素数和其他数分类讨论
\(ans=\sum_{i=1,i\not\in prime}^n\mu(i)^2-\sum_{i=1,i\in prime}^n{1}\) \(ans=\sum_{i=1}^n\mu(i)^2-\sum_{i=1}^n{2}\)

前面是积性函数前缀和,后面是素数个数。
这东西直接min25筛不就完了 为什么题解些这么麻烦啊 ?
最开始代码有点小问题,还以为不能这么做 同学帮我开了long long 竟然过了?

不过社论有\(O{\sqrt{n}}\)\(\sum\mu(i)^2\)的做法。 诶诶题解直接看这里好了link

代码

阅读全文 »

题目链接

按位看每一个数。
如果某两个数是逆序对,那必然是有一个高位不同。
如果两个数在那一位上面都\(\text{xor}\)\(1\),两个数的大小关系将会颠倒。

所以我们可以通过这种方式使逆序对变成顺序对,对于\(x\)的每一位,我们需要知道有哪些数是从这一位开始不同的,也就是这一位改变会使多少逆序对变成顺序对。

把所有数都插入\(01tire\)里面,每个节点记录一下被经过了多少次。
第一次不同无非就是某个分叉的地方,如果插入的数都是编号更小的,那么我们可以很容易计算出和当前这个数有关的顺序对和逆序对。

最后每一位都看一下\(x\)这一位的取值产生的逆序对和顺序对个数。
贪心选更少的即可。

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

const int N = (3e5 + 9) * 30;
int n, x, a[N], tr[N][2], tot;
long long inv[33], dir[33], s[N];

void insert(const int &x) {
int u = 0;
for (int i = 31; i + 1; i--) {
int c = ((x >> i) & 1);
if (!tr[u][c]) tr[u][c] = ++tot;
u = tr[u][c];
s[u]++;
}
}
void qry(const int &x) {
int u = 0;
for (int i = 31; i + 1; i--) {
int c = ((x >> i) & 1);
if (c == 0) inv[i] += s[tr[u][1]];
if (c == 1) dir[i] += s[tr[u][0]];
u = tr[u][c];
}
}

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), insert(a[i]), qry(a[i]);
long long res = 0;
int x = 0;
for (int i = 0; i <= 31; i++) {
if (inv[i] > dir[i]) x |= (1 << i), res += dir[i];
else res += inv[i];
}
printf("%lld %d\n", res, x);
return 0;
}
0%