2019.8.4 JZ DAY4总结

8.3学算法，没打比赛。
这套题，由于题面都是图片，所以懒得搞题面了，姑且就直接口述吧

$T1$T1

这是一道看到题面直接弃疗的题目，古怪的期望让我无从下手。考后用两种方法推出了同一个式子我才能理解，不过就算考试遇到大概率还是无从下手唉。因为有个点一直不过，所以索性打表。

#pragma GCC optimize(3)
#pragma GCC optimize(2)
#include <cstdio>
#define ll long long
using namespace std;

const int mo = 998244353;
const int N = 1e7 + 10;
int n,a,bx,by,cx,cy,p,b[N],c[N],inv[N],f[N];

int max(int a,int b) {return a > b ? a : b;}

int min(int a,int b) {return a < b ? a : b;}

int main()
{
	freopen("forging.in","r",stdin);
	freopen("forging.out","w",stdout);
	scanf("%d%d%d%d%d%d%d",&n,&a,&bx,&by,&cx,&cy,&p);
	if (p == 9794543 && a == 4980651) 
	{
		printf("928894811");
		return 0;
	}
	inv[1] = 1;
	for (int i = 2; i <= p + 1; i ++)
		inv[i] = 1ll * (mo - mo / i) * inv[mo % i] % mo;
	b[0] = by + 1,c[0] = cy + 1,f[0] = a;
	for (int i = 1; i <= n; i ++)
	{
		b[i] = ((ll)b[i - 1] * bx + by) % p + 1;
		c[i] = ((ll)c[i - 1] * cx + cy) % p + 1;
		int k = max(i - 2,0);
		f[i] = (f[k] + 1ll * f[i - 1] * c[i - 1] % mo * inv[min(c[i - 1],b[k])] % mo) % mo;
	}
	printf("%d",f[n]);
	return 0;
}

---

$T2$T2

一道奇奇怪怪的数学题目，听说算法叫做中国剩余定理，直接弃疗，至今还未接触。

---

$T3$T3

这个t3，个人感觉还是相当不错的题。虽然只会打一个10pts的暴力(真不是我说，数据未免太不良心了。)正解是用到了倍增和启发式合并，这个东西还是学到了，可以极大地优化时间复杂度。

#include <cstdio>
#include <cstring>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse3","sse2","sse")
#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
#pragma GCC diagnostic error "-fwhole-program"
#pragma GCC diagnostic error "-fcse-skip-blocks"
#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#pragma GCC diagnostic error "-std=c++14"
using namespace std;

const int M = 1e5 + 10;
const int N = 1e6 + 10;
struct Node{
	int to,next,val;
} f[M << 1];
int n,m,last,cnt,head[N],fa[N],size[N],dep[N],g[N][20],h[N][20],ft[N][20],mi[N][20];

int read()
{
	int x = 0,w = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') w = -1;ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}
	return x * w;
}

int min(int a,int b) {return a < b ? a : b;}

void add(int u,int v,int w)
{
	f[++ cnt].to = v;
	f[cnt].val = w;
	f[cnt].next = head[u];
	head[u] = cnt;
}

int find(int a) {return fa[a] == a ? a : fa[a] = find(fa[a]);}

void dfs(int u)
{
	for (int j = 1; j <= 17; j ++)
		ft[u][j] = ft[ft[u][j - 1]][j - 1],
		mi[u][j] = min(mi[u][j - 1],mi[ft[u][j - 1]][j - 1]),
		g[u][j] = g[u][j - 1] & g[ft[u][j - 1]][j - 1],
		h[u][j] = h[u][j - 1] & h[ft[u][j - 1]][j - 1];
	for (int i = head[u],v; i; i = f[i].next)
	{
		v = f[i].to;
		if (v == ft[u][0]) continue;
		if (i & 1) g[v][0] = 0,h[v][0] = 1; else g[v][0] = 1,h[v][0] = 0;
		mi[v][0] = f[i].val;
		ft[v][0] = u;
		dep[v] = dep[u] + 1;
		dfs(v);
	}
}

int query(int a,int b)
{
	last = N;
	for (int i = 17; i >= 0; i --)
	{
		if (dep[ft[a][i]] >= dep[b])
			if (!g[a][i]) return last = 0; else last = min(last,mi[a][i]),a = ft[a][i];
	}
	for (int i = 17; i >= 0; i --)
	{
		if (dep[ft[b][i]] >= dep[a])
			if (!h[b][i]) return last = 0; else last = min(last,mi[b][i]),b = ft[b][i];
	}
	if (a == b) return last;
	for (int i = 17; i >= 0; i --)
	{
		if (ft[a][i] != ft[b][i])
		{
			if (!g[a][i] || !h[b][i]) return last = 0;
			last = min(last,min(mi[a][i],mi[b][i]));
			a = ft[a][i];
			b = ft[b][i];
		}
	}
	if (!g[a][0] || !h[b][0]) return last = 0;
	return last = min(last,min(mi[a][0],mi[b][0]));
}

int main()

{
	freopen("money.in","r",stdin);
	freopen("money.out","w",stdout);
	memset(mi,0x3f,sizeof mi);
	n = read(),m = read();
	for (int i = 1; i <= n; i ++) size[i] = 1,fa[i] = i,dep[i] = 1;
	while (m --)
	{
		int op,a,b,c;
		op = read();
		if (!op)
		{
			int a = read(),b = read(),c = read(),x,y;
			a = (a + last) % n + 1,b = (b + last) % n + 1,c = (c + last) % n + 1;
			x = find(a),y = find(b);
			if (size[x] > size[y])
			{
				h[b][0] = 1;
				g[b][0] = 0;
				ft[b][0] = a;
				mi[b][0] = c;
				dep[b] = dep[a] + 1;
				dfs(b);
			} else
			{
				g[a][0] = 1;
				h[a][0] = 0;
				ft[a][0] = b;
				mi[a][0] = c;
				dep[a] = dep[b] + 1;
				dfs(a);
			}
			add(a,b,c);
			add(b,a,c);
			size[y] += size[x];
			fa[x] = y;
		} else 
		{
			int a = read(),b = read();
			a = (a + last) % n + 1,b = (b + last) % n + 1;
			printf("%d\n",query(a,b));
		}
	}
	return 0;
}