Summer training daily record 7.19~7.22

概率与期望

https://notes.sshwy.name/Math/Expectation/Classic/

哈夫曼树

费马点

Dilworth定理 反链定理

https://blog.csdn.net/shulianghan/article/details/109070679

牛顿迭代法优化 sqrt

组合数取模的各种方法

http://acm.hdu.edu.cn/contest/problem?cid=1098&pid=1012

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#define INF 0x3f3f3f3f
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 100, mod = 1e9 + 7;
int sum[N];
ll jie[N], res[N];
void init() {
jie[1] = 1;
jie[0] = 1;
for (int i = 2; i <= 1e6; i++) {
jie[i] = i * jie[i - 1], jie[i] %= mod;
}
}
ll qpow(ll a, ll b, ll m = mod) {
ll s = 1;
while (b) {
if (b & 1)s = (s * a) % m;
b >>= 1;
a = (a * a) % m;
}
return s % m;
}
ll inv(ll x,ll m=mod) {
x %= m;
return qpow(x, m - 2, m);
}
ll C(int n, int m) {
if (m == n)
return 1;
return (jie[m] * inv(jie[m - n] * jie[n])) % mod;
}
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
sum[i] = 0, res[i] = 0;
while (m--) {
int u, v;
cin >> u >> v;
sum[u]++, sum[v]++;
}
for (int i = 1; i <= n; i++) {
for (int j = 2; j <= sum[i]; j++) {
res[j] += C(j, sum[i]), res[j] %= mod;
}
}
ll ans = res[2];
for (int i = 3; i <= n - 1; i++) {
ans ^= res[i];
}


cout << ans <<'\n';
}
int main() {

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
init();
int t;
cin >> t;
while (t--)
solve();
return 0;
}

各种树

https://www.cnblogs.com/maybe2030/p/4732377.html

卡spfa

https://www.cnblogs.com/luckyblock/p/14317096.html

bellmon-ford
迭代n次，
for n（不超过n条边的路径）
for 所有边//松弛操作
dist[b]=min(dist[b],dist[a]+w)

spfa就是队列优化的bellman_ford算法
使用spfa判断图中是否存在负环的话，有两种方法

1. 判断一个点是不是已经进入队列了n次，由bellman_ford算法可以知道，如果不存在负环最多经过n次迭代就可以得到1到任何一个点的最短距离，一个点最多被更新n-1次

2. 判断到当前点的最短路径长度是不是大于等于n了！如果是的话，就说明存在一条路径有n的长度，那么该路径有n+1个点，必有两个点相同，所以一定存在负环
   需要注意的是判断整个图存不存在负环，并不是判断从1开始存不存在负环，所以一开始要把所有点加入到队列中
   数组模拟单链表

   #include <cstring>
   #include <iostream>
   #include <algorithm>
   #include <queue>
   using namespace std;
   const int N = 2010, M = 10010;
   
   int n, m;
   int h[N], w[M], e[M], ne[M], idx;
   int dist[N], cnt[N];
   bool st[N];
   
   void add(int a, int b, int c)
   {
       e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
   }
   
   bool spfa()
   {
       queue<int> q;
   
       for (int i = 1; i <= n; i ++ )
       {
           st[i] = true;
           q.push(i);
       }
   
       while (q.size())
       {
           int t = q.front();
           q.pop();
   
           st[t] = false;
   
           for (int i = h[t]; i != -1; i = ne[i])
           {
               int j = e[i];
               if (dist[j] > dist[t] + w[i])
               {
                   dist[j] = dist[t] + w[i];
                   cnt[j] = cnt[t] + 1;
   
                   if (cnt[j] >= n) return true;
                   if (!st[j])
                   {
                       q.push(j);
                       st[j] = true;
                   }
               }
           }
       }
   
       return false;
   }
   
   int main()
   {
       scanf("%d%d", &n, &m);
       memset(h, -1, sizeof h);
       while (m -- )
       {
           int a, b, c;
           scanf("%d%d%d", &a, &b, &c);
           add(a, b, c);
       }
       if (spfa()) puts("Yes");
       else puts("No");
       return 0;
   }

vector存图

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector> 
#include<queue>
using namespace std;
const int N = 2010;
const int INF = 0x3f3f3f3f;
int n, m;
bool st[N];
int dist[N];
int cnt[N];
struct VER
{
	int to;
	int w;
};
vector<VER> h[N];

void add(int a, int b, int w)
{
	VER ver;
	ver.to = b;
	ver.w  = w;
	h[a].push_back(ver);
}

bool spfa()
{
// 	memset(dist, 0x3f, sizeof dist);
// 	dist[1] = 0;
	
	queue<int> q;
	// 所有点都入队 
	for(int i = 1; i <= n; i++)
	{
		st[i] = true;
		q.push(i);
	}
	
	while(q.size())
	{
		int t = q.front();
		q.pop();
		st[t] = false;
		if(cnt[t] >= n) return true;
		for(int i = 0; i < h[t].size(); i++)
		{
			int j = h[t][i].to, w = h[t][i].w;
			if(dist[j] > dist[t] + w)
			{
				dist[j] = dist[t] + w;
				cnt[j] = cnt[t] + 1; // t->j路径长度+1 
				if(!st[j]) // j不在队列中 
				{
					q.push(j);
					st[j] = true;
				}	
			}	
		} 
	}
	return false;
}	

int main()
{
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int a, b, w;
		scanf("%d%d%d", &a, &b, &w);
		add(a, b, w);
	}
	bool t = spfa();
	if(t) puts("Yes");
	else  puts("No");
	return 0;
}

图和树的概念整理

https://blog.csdn.net/weixin_45697774/article/details/104495126
https://blog.csdn.net/weixin_45697774/article/details/105352366

链式向前星 存图

https://blog.csdn.net/lookqaq/article/details/81304637

向前星：边集数组
所有边首先按照起点从小到大第一次序排列，然后按照终点从小到大第二次序排列
并记录以i为起点的边的数量(len[i])，和所有符合条件的边的在数组中的起始位置(head[i])
主要用于优化spfa,dfs,bfs;
因为需要排序操作，使用快排时间至少为O（nlogn）

链式向前星：优化了排序的向前星

struct Edge
{
     int next;
     int to;
     int w;
};
其中edge[i].to表示第i条边的终点,edge[i].next表示与第i条边同起点的下一条边的存储位置,edge[i].w为边权值.
另外还有一个数组head[i],存储所有符合起点为i的边的在数组中的起始位置
head[]数组一般初始化为-1,对于加边的add函数是这样的:
void add(int u,int v,int w)//起点u，终点v，边权重w
{
    edge[cnt].w = w;
    edge[cnt].to = v;
    edge[cnt].next = head[u]//与第cnt条边同起点(u)的下一条边的存储位置
    head[u] = cnt++;
}

模拟输入输出
1 2
2 3
3 4
1 3
4 1
1 5
4 5
得到（cnt=0）
edge[0].to = 2; edge[0].next = -1; head[1] = 0;//
edge[1].to = 3; edge[1].next = -1; head[2] = 1;
edge[2].to = 4; edge[2],next = -1; head[3] = 2;
edge[3].to = 3; edge[3].next = 0; head[1] = 3;//
edge[4].to = 1; edge[4].next = -1; head[4] = 4;
edge[5].to = 5; edge[5].next = 3; head[1] = 5;//
edge[6].to = 5; edge[6].next = 4; head[4] = 6;
例如起点为1的边，读取head[1]=5,从5——>3——>0链式逆序回溯

struct node
{
    ll v,nex,val,u;
}e[N];

ll head[N],cnt;

inline void add(ll u,ll v,ll val)//从u到v，从父节点到子节点
{
    e[++cnt].nex=head[u];
    e[cnt].val=val;//可有可无
    e[cnt].v=v;
    e[cnt].u=u;//可有可无
    head[u]=cnt;
}
for(ll i=head[u];i;i=e[i].nex)
    {
        ll v=e[i].v;
        ---------------
    }

//这样我们就可以遍历全部的点了！！！：）

二分图/二部图

01背包朴素优化

只需要用到上一层或者下一层状态时，在两个状态（0·1）之间轮流转化
利用滚动数组 或者代码的等价变形优化

https://www.acwing.com/solution/content/52491/

Donate