清北澡堂2020十一刷题Day6解题报告

清北澡堂2020十一刷题Day6 解题报告

[数竞题?]T1 math

小蓝本救命

大意

求$\gcd(q^a-1,q^b-1)\mod p$

Sol

辗转相除法的原理是$\gcd{(a, b)} = \gcd{(b, a\mod b)}$，其实就是$\gcd{(a, b)} = \gcd{(b, a-b-b-\cdots-b)}=\gcd{(b, a-\lfloor\frac{a}{b}\rfloor\cdot b)}$

假设$a>b$，原式可以化为$\gcd(q^b-1, q^a-q^b)$

其中，$q^a-q^b=q^b\cdot(q^{a-b}-1)$，又因为$q^b-1$一定与$q^b$互质，所以$\gcd(q^b-1, q^a-q^b)=\gcd(q^b-1,q^{a-b}-1)$

我们再次使$a’=b,b’=a-b$，上式可以化成$\gcd{(q^{a’}-1, q^{b’}-1)}$，一直推下去，可以得到

$\gcd(q^a-1,q^b-1)=\gcd{(q^0-1,q^{\gcd{(a,b)} }-1)}=q^{\gcd{(a,b)} }-1$(参考辗转相除法的做法)

最后注意判断下答案小于$0$时的输出即可

Code

res = ksm(q, gcd(a, b), p) - 1;
printf("%lld\n", res < 0 ? res + p : res);

T2 candy

其实正解就是暴力优化一下

想到Dinic里的当前弧优化

令$cur_t$表示当前$t$能吃的最后一个糖果

下次从这里开始找即可

Code

scanf("%d", & n);
for (int i = 1, t; i <= n; ++i)
    scanf("%d", & t),
    ++cnt[t];
scanf("%d", & m);
for (int i = 1, t; i <= m; ++i) {
    scanf("%d", & t);
    for (int j = curl[t]; j <= 1e6; j += t)
        if (cnt[j]) {
            ans[i] = j,
            --cnt[j],
            curl[t] = j;
            break;
        }
    if (!ans[i]) {
        printf("%d\n", i - 1);
        for (int j = 1; j < i; ++j)
            printf("%d ", ans[j]);
        puts("");
        return 0;
    }
}

当然似乎也可以预处理一下每个数的因子

T3 lagrange

推式子真快乐

大意

给定$A_i,B_i$，带修改$A_i,B_i$，

求$\sum\limits_{l\leq i < j\leq r}{(A_iB_j-A_jB_i)^2} \mod 998244353$

Sol

首先对原式展开平方，得到

$$\sum\limits_{i<j}{(A_iB_j-A_jB_i)^2}=\sum\limits_{i<j}{(A_i^2B_j^2+A_j^2B_i^2)}-2\sum\limits_{i<j}{A_iA_jB_iB_j}$$

把它分成左右两个部分

对于左边部分，可以借助容斥的思想进行变换，得到¹

$$\sum\limits_{i<j}{(A_i^2B_j^2+A_j^2B_i^2)}=\sum\limits_{i\neq j}{A_i^2B_j^2}=\sum{A_i^2B_j^2}-\sum{A_i^2B_i^2}$$

右边部分，我们设$C_i=A_iB_i$，那么有²

$$2\sum\limits_{i<j}{A_iA_jB_iB_j}=\sum\limits_{i\neq j}{C_iC_j}=\sum{C_iC_j}-\sum{C_i^2}$$

将$C_i=A_iB_i$带入，得到

$$2\sum\limits_{i\neq j}{A_iA_jB_iB_j}=\sum{A_iA_jB_iB_j}-\sum{A_i^2B_i^2}$$

所以，原式

$$\begin{align*} &=\sum{A_i^2B_j^2}-\sum{A_i^2B_i^2}-\sum{A_iA_jB_iB_j}+\sum{A_i^2B_i^2}\\ &=\sum{(A_i^2B_j^2-A_iA_jB_iB_j)}\\ &=\sum{A_i^2}\cdot\sum{B_i^2}-(\sum{A_iB_i})^2\\ \end{align*}$$ $$\therefore\ \sum\limits_{l\leq i < j\leq r}{(A_iB_j-A_jB_i)^2}=\sum\limits_{l\leq i\leq r}{A_i^2}\cdot\sum\limits_{l\leq i\leq r}{B_i^2}-(\sum\limits_{l\leq i\leq r}{A_iB_i})^2$$

使用树状数组进行维护即可（其实这玩意就是拉格朗日恒等式）

¹. $\begin{align}\sum{a_i}\cdot\sum{b_i}&=(a_1\cdot a_2\cdots a_n)\cdot(b_1\cdot b_2\cdots b_n)\\&=a_1b_1+a_1b_2+\cdots+a_nb_n\\&=\sum\limits_{i,j}{a_ib_j}\\&=\sum\limits_{i<j}{(a_ib_j+a_jb_i)}+\sum{a_ib_i}\\&=\sum\limits_{i\leq j}{(a_ib_j+a_jb_i)}-\sum{a_ib_i}\end{align}$ ↩

². $\begin{align}&\because c_i=c_j\\&\therefore c_i\cdot c_j=c_j\cdot c_i\\&\therefore\sum\limits_{i<j}{c_i\cdot c_j}=\frac{\sum{c_i}\cdot\sum{c_i}-\sum{c_i^2} }{2}\\&\quad\sum\limits_{i<j}{c_i\cdot c_j}=\frac{\sum{c_i}\cdot\sum{c_i}-\sum{c_i^2} }{2}\end{align}$ ↩

Code

及时取模 别爆long long

read(n, q);
for (register int i = 1; i <= n; ++i)
    read(a[i]),
    a[i] %= mod;
for (register int i = 1; i <= n; ++i)
    read(b[i]),
    b[i] %= mod;
for (register int i = 1; i <= n; ++i)
    update(treea, i, a[i] * a[i] % mod),
    update(treeb, i, b[i] * b[i] % mod),
    update(treeab, i, a[i] * b[i] % mod);
while (q--) {
    read(opt);
    if (opt == 1) {
        read(l, r),
        res = query(treea, l, r) % mod * query(treeb, l, r) % mod - pow(query(treeab, l, r) % mod);
        while (res < 0)
            res += mod;
        printf("%lld\n", res);
    } else {
        read(x, l, r),
        update(treea, x, (l % mod * l % mod) - (a[x] * a[x] % mod)),
        update(treeb, x, (r % mod * r % mod) - (b[x] * b[x] % mod)),
        update(treeab, x, (l % mod * r % mod) - (a[x] * b[x] % mod)),
        a[x] = l % mod,
        b[x] = r % mod;
    }
}