杜教筛

求 $\sum_{i=1}^{n} \phi(i^2)$

基本上是裸的杜教筛

一个关于 $\phi$ 的性质：$$\phi(ij) = \frac{\phi(i)\phi(j)gcd(i,j)}{\phi(gcd(i,j))}$$

证明：该式本质上是容斥，$\phi$ 的原式子是，当 $n = {p_1}^{c_1}\times {p_2}^{c_2} \times ··· \times {p_m}^{c_k}$

$\phi(n) = n \times \prod_{i=1}^{m} (1 - \frac{1}{p_i})$

这里式子就表示为先把 $i$ 和 $j$ 的质因数乘上在除去 $i,j$ 的共同质因数，即 $\phi(gcd(i,j))$，最后再消掉 $gcd(i,j)$ 即可得到该式。

然后开始推式子：

$$ \sum_{i=1}^{n} \phi(i^2) = \sum_{i=1}^{n} i \times \phi(i) $$

不难发现该式等于 $\phi \cdot id$

$$ (\phi \cdot id) \ast id = \sum_{d\mid n} d * \phi(d) * \frac{n}{d} = n \times \sum_{d\mid n} \phi(d) = id^2$$

我们设 $f(n) = n \times \phi(n),S(n) = \sum_{i=1}^{n} f(i)$ ,这里的 $id$ 与 $id^2$ 的前缀和都比较好求。

运用杜教筛公式可得：

$$ S(n) = \sum_{i=1}^{n}i^2 - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)$$

$$ = \frac{n(n+1)(2n+1)}{6} - \sum_{i=2}^{n} i * S(\lfloor\frac n i\rfloor)$$

线性筛出前 $n^{\frac{2}{3}}$ 项，整除分块即可

挺好的递推+恶心的矩阵快速幂题

题面:有一个n行m列的棋盘,在当前位置可以瞬移，每次可向右瞬移奇数列，且瞬移到本行或相邻行，并且不能瞬移出棋盘，问从$(1,1)至(n,m)$的总方案数

首先考虑递推，设$f(i,j)$为投当前在第i行第j列的方案数，因为每次可以向右瞬移，所以$f(i,j)$可以由上一列,上上上一列...推出来,且可以由上一行和下一行推出

则递推转移方程式为$f(i,j) = \sum_{k=j-w,w=1,w+=2}^j f(i,k)+f(i-1,k)+f(i+1,k)$

这样直接枚举是$O(nm^2)$的复杂度，肯定是不行的，那我们继续考虑

我们设$g(i,j) = \sum_{k=j-w,w=1,w+=2}^j f(i,k) = g(i,j-2) + f(i,j-1)$

则方程式转为$f(i,j) = g(i-1,j) + g(i,j) + g(i+1,j) = g(i-1,j-2) + f(i-1,j-1) + g(i,j-2) + f(i,j-1) + g(i+1,j-2) + f(i+1,j-1)$

我们在维护$f$的同时维护$g$则时间复杂度会降到$O(nm)$

一看数据$10^9$，再次拿出我们的dz，一眼鉴定为矩阵快速幂

然后就开始我们快(恶)乐(心)的推转移矩阵的时候：

根据转移方程我们可以分成两种情况，即上一列的方案和上上一列的方案，因为上上一列的方案数在推下一列的方案数时要用到，所以不能去掉，我们都需要记录，所以需要当推到$f(i,j)$时，我们需要$f(i,j-1)， g(i,j-1)， g(i,j-2)$把这三列归为一列，$1至n$为$f(i,j-1)$，$n+1至2n$为$g(i,j-1)$，$2n+1至3n$为$g(i,j-2)$最后该矩阵的长度为$3n$最大为150，则我们转移矩阵大小为$3n * 3n$

先看应该怎样转移

$$\begin{bmatrix}f(1,j-1) & f(2,j-1) & ... & f(n,j-1) & g(1,j-1) & g(2,j-1) & ... & g(n,j-1) & g(1,j-2) & g(2,j-2) & ... & g(n,j-2) \\\end{bmatrix}$$

应该转移为

$$\begin{bmatrix}f(1,j) & f(2,j) & ... & f(n,j) & g(1,j) & g(2,j) & ... & g(n,j) & g(1,j-1) & g(2,j-1) & ... & g(n,j-1) \\\end{bmatrix}$$

所以根据递推转移方程考虑转移矩阵，则可推出矩阵为:

设转移矩阵为$c(i,j)$

首先先看f的矩阵:根据递推方程 当$f(i,j)$时 只需将$c(i-1,i),c(i,i),c(i+1,i)$设为1,才加上$g$即将$c(2*n+i-1,i),c(2*n+i,i),c(2*n+i+1,i)$再设为1就可以了

再考虑$g(i,j)$ 由递推方程式得 应当将$c(i,i+n),c(i+2*n,i+n)$置为1即可

最后看$g(i,j-1)$ 在转移前已经出现，不需要推，所以只要将$c(i+n,i+2*n)$置为1即可

（因为矩阵实在太大画不下，只好描述一下）

Oo最后开始愉悦的矩阵快速幂时刻oO

复杂度为$O(150^3*log(1e9))$，大约为$1e8$所以跑的飞慢qwq

二维递推实在痛苦┭┮﹏┭┮

挺好的递推+矩阵快速幂题

题面:有一个m面的骰子,问投n次使投到第6面为偶数次的方案数

首先考虑递推，设f(i,j,k)为投i次的情况，j为0或1 (0为本次未投到第6面,1为投到了)，k为0或1 (当前投到第6面次数的奇和偶,0为偶,1为奇)

转移方程为$f(n,1,0) = f(n-1,1,1) + f(n-1,0,1)$

$f(n,1,1) = f(n-1,1,0) + f(n-1,0,0)$

$f(n,0,0) = m-1 * f(n-1,1,0) + m-1 * f(n-1,0,0)$

$f(n,0,1) = m-1 * f(n-1,1,1) + m-1 * f(n-1,0,1)$

看到n的范围$10^{18}$ wow，一眼dz，肯定要快速幂,根据递推可以想到矩阵快速幂，下面开始推转移矩阵

可以想到

$$\begin{bmatrix}f(n-1,1,0) & f(n-1,1,0) & f(n-1,0,0) & f(n-1,0,1) \\\end{bmatrix}$$

应该转移为

$$\begin{bmatrix}f(n,1,0) & f(n,1,0) & f(n,0,0) & f(n,0,1)\end{bmatrix}$$

所以根据递推转移方程考虑转移矩阵，则可建出矩阵为:

$$\begin{bmatrix}0 & 1 & m-1 & 0\\1 & 0 & 0 & m-1\\0 & 1 & m-1 & 0\\1 & 0 & 0 & m-1\\\end{bmatrix}$$

初始矩阵为$f(1)$ 即 $\begin{bmatrix}0 , 1 , m-1 , 0\end{bmatrix}$

OO最后直接跑矩阵快速幂就行了OO

复杂度为$O(4^3*log(n))$

好像这道题还有数学方法,但不会

本题另一种做法:二分图

题目描述中可知要找最小的值，即任意两个大于该值的罪犯都应该被分在两个不同的监狱，这样就可以想到二分图，先二分，将大于mid的边全部连上，直接判断二分图

如若是，则r = mid,否则l = mid+1

这道题的思路比较简单，就不说了(除了代码有些长)

主要是总结一下tarjan求强连通分量的用法总结:
1.就是tarjan模板题例

·1.619. [金陵中学2007] 传话和1001. [WZOI 2011 S3] 消息传递（一道题，重复了）

·2.921. [東方S1] 上白泽慧音 和 1298. 通讯问题（+存储scc）

2.有些思维的tarjan题

·1.3810. [USACO Open22 Silver]Visits(环内处理)

·2.1870. [国家集训队2011]稳定婚姻（怎么建有向图）

3.tarjan后对DAG图(有向无环图)的处理

·1.关于出度入度问题的

 ·449. 网络病毒 和 908. [USACO 5.3] 校园网(3275. [POJ 1236]学校网络 又重复了:()

 ·1175. [顾研NOIP] 旅游电车

·2.缩点后处理的

 ·2229. 正则表达式（缩点后跑最短路）

 ·3644. [POJ 2762]从u到v还是从v到u？(缩点后拓扑序)

4.tarjan与其他的结合

 ·3645. [BZOJ 2438]杀人游戏(与概率相关)

5.tarjan进阶2-SAT(模板洛谷https://www.luogu.com.cn/problem/P4782)

 ·3452. POJ 3678]卡图难题(xor，or，and结合)

前置知识:tarjan求强连通分量

先看题，大意是2n个人中当一对夫妻离婚后，剩下可不可以再次组成n对情人

我们先将所有的丈夫和妻子用连接起来，表示他们之间存在着联系(即无向图)，如果这时如果也把曾经的情人按照这种方法连起来，那么他们之间也存在着这种联系，但这两种情况可以认为是相同的（无向图中边没有差异），可以发现出现了一些环，而处在环中的几对夫妻都可以在离婚后组成情人，也就是题目中所说的婚姻不安全。那么我们找出这些环，判断哪些夫妻处在环中即可。

对于找环，我们想到了Tarjan求强连通分量，但是这个算法是在有向图上进行的，于是我们尝试给我们连接出的无向图定向，但如果只是按照女→男的方法我们可以发现是不对的，因为这些边也是相同的

所以我们可以这样建图：

夫妻之间：girl→boy而情人之间：boy→girl

这样只要不安全就可以形成一个环,可以用tarjan求强连通分量解

最后判断对于一对夫妻，如果两人在同一个强连通分量里，那么这对婚姻就是不安全的，反之安全

至于字符串处理，因为题目给出每对夫妻不会重复所以只需要将第i对夫妻的男女当成编号为i*2-1和i*2，再用map进行储存编号就可以了

#include <bits/stdc++.h> 
using namespace std;
//强连通分量思维题+字符处理map 
const int N = 8e3+10,M = 2e4+10;//N的范围开大一倍 
int n,m;
struct made{
    int ver,nx;
}e[M<<1];//M也要开大 
int hd[N],tot,cnt,num,top;
int low[N],dfn[N],st[N],color[N];
bool v[N];
string c1[N],c2[N];
map<string,int>mp;
void add(int x,int y){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],hd[x] = tot;
}
void tarjan(int x){
    low[x] = dfn[x] = ++cnt;
    st[++top] = x,v[x] = 1;
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        if(!dfn[y])tarjan(y),low[x] = min(low[x],low[y]);
        else if(v[y])low[x] = min(low[x],dfn[y]);
    }
    if(low[x] == dfn[x]){
        num++;int y = 0;
        do{
            y = st[top--];
            v[y] = 0,color[y] = num;
        }while(x != y);
    }
}
int main(){
    freopen("marriage.in","r",stdin);
    freopen("marriage.out","w",stdout);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        string x,y;cin>>c1[i]>>c2[i];
        add(i*2-1,i*2);//夫妻由女方指向男方 
        mp[c1[i]] = i*2-1;
        mp[c2[i]] = i*2;
    }
    scanf("%d",&m);
    for(int i = 1;i <= m;i++){
        string x,y;cin>>x>>y;
        add(mp[y],mp[x]);//情人由男方指向女方,这样只要不安全就可以形成一个环,可以用强连通分量解 
    }
    for(int i = 1;i <= 2*n;i++)
        if(!color[i])tarjan(i);
    for(int i = 1;i <= n;i++){
        if(color[i*2-1] == color[i*2])printf("Unsafe\n");//
        else printf("Safe\n");
    }
    
    return 0;
    
}