qwq

luogu 3958

int a[4] = {1, 2, 3, 4};
    do{
        for(int i = 0; i < 4; ++i) cout<<a[i]<<" ";
        cout<<endl;
    } while(next_permutation(a, a + 4));

$3 \equiv 5 \pmod 2$

$111 \cdots 1 \equiv K \pmod m$

$\frac{10^n - 1}{9} \equiv K \pmod m$

$10^n \equiv 9 K + 1 \pmod m$

最小的N 使得 $10^N \mod m = 9K + 1$

$1 + 10 + 100 + \cdots + 10^n = \frac{1 - 10^n}{1 - 10}$

$a ^ b = a^{b/2} * a^{b/2} * a, b \mod 2 = 1$

#define LL long long
LL ksm(LL a, LL n, LL m) { //a^n % m
    LL ans = 1;
    while(n) {
        if(n % 2 == 1) ans = ans * a % m;
        a = a * a % m;
        n /= 2;
    }
    return ans;
}

fake T3

1111100011 % K = x

n 1 m 0

$p^n \cdot (1-p)^m$

$x \% m = \lambda$

$a[\lambda] += p^n \cdot (1-p)^m$

前缀和

$s[i] = a[i] + s[i-1]$

$q(l, r) = s[r] - s[l-1]$

1 2 3 4 5
[2, 4] + 2 -> 1 4 5 6 5
[1, 3] + 1 -> 2 5 6 6 5

cf[i] 0 0 0 0 0
0 2 0 0 -2 -> 0 2 2 2 0
1 2 0 -1 -1 -> 1 3 3 2 0

0 2 2 2 0 cf[i] = a[i] - a[i-1]
0 2 0 0 -2

3 4 5 6 7 -> 12
5 6 7 7 -> 30
7 7 11 -> 49
11 14 -> 154
25

T1

map + 暴力模拟

$10^5$？

T2

$(a + b)^2 = a^2 + 2ab + b^2$

$(a + b + c)^2 = a^2 + b^2 + c^2 + 2ab + 2ac + 2bc$

$(a + b + c + d)^2 =$

$\sum_{1 \le a \ne b \le n} ab = \frac{(\sum i)^2 - \sum i^2}{2}$

$\sum_{L \le i \ne j \le R} a_ia_j = \frac{(\sum_{L \le i \le R} a_i)^2 - \sum_{L \le i \le R} a_i^2}{2}$

龟速乘法

$a\times b \% p$

取模 模2p ->超时

$a_1 a_2$

$a_1a_2 + a_1a_3 + a_2a_3 = a_1a_2+a_3(a_2+a_1)$

$a_2a_1 + a_3(a_1+a_2) + ...+a_n(a_1 + a_2 +...)$

$a_{L+1}a_L + a_{L+2}(a_L+a_{L+1})+...$$+a_R(a_L + a_{L+1} +...+ a_{R-1})$

$a_{L+1}(S_L - S_{L-1}) + a_{L+2}(S_{L+1} - S_{L-1}) + ...$

$a_{L+1}S_L + a_{L+2}S_{L+1} +... + a_{R}S_{R-1} - S_{L-1}(S_R - S_L)$

$b_i = a_{i+1}S_i$ 前缀和 $SS_i$

$SS_{R} - SS_{L} - S_{L-1}(S_R - S_L)$

T3

对于$40\%$，裸的并查集

观察到，对于$[L, R]$中的子图数量=点的数量- 端点在区间中的边的数量

对另外$20\%$，$L = 1$，这个时候可以直接拖动右端点来加边。问题转化为了求解端点在$[L, R]$内的边的数量。

以此为启发，我们可以考虑莫队来实现add和del操作，寻找每一个加入或删除的点的连边在区间内的数量，复杂度期望$O(n\sqrt n)$，但是会被没有随机生成的数据点卡掉，可以得到80分。

对于$100\%$，首先将操作离线，离线之后同样每次拖动右端点，更新右端点连向的编号小于本身的点，然后如果询问的右端点为该点本身，则输出$Query(R) - Query(L-1)$，可以使用树状数组维护。这样可以消除后效性，复杂度$O(n\log n)$