UOJ73 【WC2015】未来程序

题目描述：给出输入和暴力程序，求输出。共10个测试点。

测试点1：

输入\(a,b,c\)，求\(a\times b \ \mathrm{mod} \ c\)

\(a,b,c\)属于long long范围。

使用龟速乘或者快速乘。

#include<bits/stdc++.h>

#define Rint register int

using namespace std;

typedef long long LL;

LL a, b, mod;

inline void upd(LL &a, LL b){a += b; if(a >= mod) a -= mod;}

inline LL mul(LL a, LL b){

	LL res = 0;

	while(b){

		if(b & 1) upd(res, a);

		upd(a, a); b >>= 1;

	}

	return res;

}

int main(){

	freopen("program1.in", "r", stdin);

	freopen("program1.out", "w", stdout);

	for(Rint i = 1;i <= 10;i ++){

		scanf("%lld%lld%lld", &a, &b, &mod); a %= mod; b %= mod;

		printf("%lld\n", mul(a, b));

	}

}

测试点2：发现它就是个线性递推，暴力矩阵快速幂即可。

#include<bits/stdc++.h>

#define Rint register int

#define int unsigned

using namespace std;

typedef long long LL;

const int N = 3;

LL n;

int mod;

inline void upd(int &a, int b){a += b; if(a >= mod) a -= mod;}

inline int add(int a, int b){return (a + b >= mod) ? (a + b - mod) : (a + b);}

inline int sub(int a, int b){return (a < b) ? (a + mod - b) : (a - b);}

struct Matrix {

	int a[N][N];

	inline Matrix(){memset(a, 0, sizeof a);}

	inline Matrix operator * (const Matrix &o) const {

		Matrix res;

		for(Rint i = 0;i < N;i ++)

			for(Rint k = 0;k < N;k ++)

				for(Rint j = 0;j < N;j ++)

					upd(res.a[i][j], (LL) a[i][k] * o.a[k][j] % mod);

		return res;

	}

} A, B, C;

inline Matrix kasumi(Matrix A, LL n){

	Matrix res;

	for(Rint i = 0;i < N;i ++) res.a[i][i] = 1;

	while(n){

		if(n & 1) res = res * A;

		A = A * A; n >>= 1;

	}

	return res;

}

signed main(){

	freopen("program2.in", "r", stdin);

        freopen("program2.out","w",stdout);

	A.a[0][0] = A.a[0][2] = A.a[1][0] = A.a[1][1] = A.a[2][0] = B.a[0][0] = 1; A.a[0][1] = 2;

	for(Rint i = 1;i <= 10;i ++){

		cin >> n >> mod;

		C = kasumi(A, n) * B;

		cout << add(sub(C.a[0][0], C.a[1][0]), sub(C.a[2][0], C.a[1][0])) << endl;

	}

}

测试点3：

输入\(n=10^{15}\)，求\(\sum_{i=1}^ni^k \ \mathrm{mod} \ 2^{64}(k=0,1,2,3,4)\)

\[\begin{aligned}
\sum_{i=1}^ni^0&=n \\
\sum_{i=1}^ni^1&=\frac{n(n+1)}{2} \\
\sum_{i=1}^ni^2&=\frac{n(n+1)(2n+1)}{6} \\
\sum_{i=1}^ni^3&=(\frac{n(n+1)}{2})^2 \\
\sum_{i=1}^ni^4&=\frac{n(n+1)(2n+1)(3n^2-3n+1)}{30}
\end{aligned}
\]

首先用__int128求出\(\frac{n(n+1)}{2}\)，然后求出\(\frac{1}{3}\)和\(\frac{1}{15}\)，直接计算。

#include<bits/stdc++.h>

#define Rint register int

using namespace std;

typedef unsigned long long LL;

typedef __int128 LLL;

LL n, m;

inline LL kasumi(LL a, LL b){

	LL res = 1;

	while(b){

		if(b & 1) res *= a; a *= a; b >>= 1;

	}

	return res;

}

LL inv3 = kasumi(3, (1ull << 63) - 1);

LL inv15 = kasumi(15, (1ull << 63) - 1);

int main(){

	scanf("%llu", &n); m = (LLL) n * (n + 1) / 2;

	printf("%llu\n", n); printf("%llu\n", n);

	printf("%llu\n", m); printf("%llu\n", m);

	printf("%llu\n", m * (2 * n + 1) * inv3); printf("%llu\n", m * (2 * n + 1) * inv3);

	printf("%llu\n", m * m); printf("%llu\n", m * m);

	printf("%llu\n", m * (2 * n + 1) * (3 * n * n + 3 * n - 1) * inv15);

	printf("%llu\n", m * (2 * n + 1) * (3 * n * n + 3 * n - 1) * inv15);

}

测试点4：

输入\(n\times m\)的随机01矩阵，有两个问题：

求\(1\)的个数\(ans\)，输出\(\frac{ans(ans-1)}{2}\)
对于每个\(1\)，求离它最近的\(0\)的距离之和（曼哈顿距离）

\(1\le n,m\le 1000\)

看上面的粗体字。

#include <iostream>

const int N = 5000, inf = 0x3F3F3F3F;

int n, m, type;

bool data[N + 11][N + 11];

int seed;

int next_rand(){

	static const int P = 1000000007, Q = 83978833, R = 8523467;

	return seed = ((long long)Q * seed % P * seed + R) % P;

}

void generate_input(){

	std::cin >> n >> m >> type;

	for(int i = 0; i < n; i++)

		for(int j = 0; j < m; j++)

			data[i][j] = bool((next_rand() % 8) > 0);

}

long long count1(){

	long long ans = 0LL;

	for(int i = 0; i < n; i++)

		for(int j = 0; j < m; j++)

			if(data[i][j]) ++ ans;

	return ans * (ans - 1);

}

int abs_int(int x){

	return x < 0 ? -x : x;

}

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

long long count2(){

	long long ans = 0LL;

	for(int i = 0; i < n; i++)

		for(int j = 0; j < m; j++)

			if(data[i][j])

				for(int k = 1;k <= n + m - 2;k ++){

					bool flag = false;

					for(int x = max(i - k, 0); x <= i + k && x < n && !flag; x ++){

						int y = j - (k - abs(i - x));

						if(y >= 0 && y < m && !data[x][y]) flag = true;

						y = j + (k - abs(i - x));

						if(y >= 0 && y < m && !data[x][y]) flag = true;

					}

					if(flag){ans += k; break;}

				}

	return ans;

}

int main(){

	freopen("program4.in", "r", stdin);

	freopen("program4.out", "w", stdout);

	std::cin >> seed;

	for(int i = 0; i < 10; i++){

		generate_input();

		std::cout << (type == 1 ? count2() : count1()) << std::endl;

	}

	return 0;

}

测试点5：

输入\(n\times m\)的随机01矩阵，求有多少个全1子矩阵。

\(1\le n,m\le 5000\)

是不是觉得很熟悉？

#include<bits/stdc++.h>

#define Rint register int

using namespace std;

typedef long long LL;

const int N = 5003;

int seed;

int next_rand(){

	static const int P = 1000000007, Q = 83978833, R = 8523467;

	return seed = ((long long)Q * seed % P * seed + R) % P;

}

int n, a[N][N], pre[N][N], stk[N], top;

LL ans1;

int main(){

	freopen("program5.in", "r", stdin);

	freopen("program5.out", "w", stdout);

	scanf("%d", &seed);

	for(Rint T = 1;T <= 10;T ++){ ans1 = 0;

	scanf("%d", &n); scanf("%d", &n);

	for(Rint i = 1;i <= n;i ++)

		for(Rint j = 1;j <= n;j ++)

			a[i][j] = next_rand() & 7;

	for(Rint i = 1;i <= n;i ++)

		for(Rint j = 1;j <= n;j ++)

			if(a[i][j]) pre[i][j] = pre[i - 1][j] + 1;

			else pre[i][j] = 0;

	for(Rint i = 1;i <= n;i ++){

		LL ans = 0; top = 0;

		for(Rint j = 1;j <= n;j ++){

			ans += pre[i][j];

			while(top && pre[i][j] <= pre[i][stk[top]]){

				ans -= (LL) (pre[i][stk[top]] - pre[i][j]) * (stk[top] - stk[top - 1]);

				-- top;

			}

			stk[++ top] = j;

			ans1 += ans;

		}

	}

	printf("%lld\n", ans1);

	}

}

测试点6：

输入\(n,a,b,c\)，设\(f_0=0,f_n=(af_{n-1}^2+b) \ \mathrm{mod} \ 2^{64} \ \mathrm{mod} \ c\)，求\(f_n\)

\(n,a,b,c\)在long long范围内。

有个东西叫做floyd判圈算法。这个算法可以在线性时间复杂度内计算自动机/迭代函数/链表（每个点只有一条出边的有向图）上面的环。

直接讲做法了：首先从\(S\)出发，然后设两个指针\(x,y\)，一个快指针和一个慢指针，快指针每次走\(2\)步，慢指针每次走\(1\)步，然后它们在\(M\)点相遇。

计算环长：令其中一个指针一直走，记录步数。

计算环起点：令其中一个指针在\(M\)，另一个在\(S\)，然后以同样的速度走。

然而如果你跑这东西的话会耗死你。【我都写完上面的东西了它一个数据点都没跑出来】

需要用一个Brent判环算法。这东西的过程是这样的。

首先定义一个步长\(step=2\)，当前步数\(cnt\)，一个![img](file:///C:\Users\86158\AppData\Local\Temp\SGPicFaceTpBq\4356\1BE49467.png)指针\(x\)和一个![img](file:///C:\Users\86158\AppData\Local\Temp\SGPicFaceTpBq\4356\1BDDB9F2.png)指针\(y\)。

让\(x\)一直跑，遇到\(y\)的时候退出，\(cnt\)环长。
否则让\(step=step\times 2,y=x,cnt=0\)

知道环长之后，令\(x=y=0\)，然后让\(x\)跑\(cnt\)遍，然后再让\(x,y\)一起跑，相遇的地方就是环起点。

然后从环起点开始跑就可以了。

#include<bits/stdc++.h>

#define Rint register int

using namespace std;

typedef unsigned long long LL;

const LL N = 1e10;

LL n, a, b, c;

inline LL nxt(LL x){return (x * x * a + b) % c;}

int main(){

	freopen("program6.in", "r", stdin);

	freopen("program6.out", "w", stdout);

	for(Rint T = 1;T <= 10;T ++){

		scanf("%llu%llu%llu%llu", &n, &a, &b, &c);

		LL s = 0, r = 2, x = 0, y = 0, cnt = 0;

		while(true){

			y = nxt(y); ++ s;

			if(x == y) break;

			if(s == r){x = y; s = 0; r <<= 1;}

		}

		x = y = 0;

		while(cnt < s) x = nxt(x), ++ cnt;

		cnt = 1;

		while(x != y) x = nxt(x), y = nxt(y), ++ cnt;

		r = (n - cnt) % s + 1;

		while(r --) x = nxt(x);

		printf("%llu\n", x);

	}

}

测试点7：

\(16*16\)的数独。

是不是觉得很熟悉？

#include<cstdio>

#include<cstring>

#define Rint register int

using namespace std;

const int N = 1000003, n = 4096, m = 1024;

int a[17][17], r[N], u[N], l[N], d[N], s[N], col[N], row[N], h[N], ans[N], cnt;

inline void init(){

	for(Rint i = 0;i <= m;i ++){

		l[i] = i - 1; r[i] = i + 1;

		u[i] = d[i] = i;

	}

	l[0] = m; r[m] = 0;

	memset(h, -1, sizeof h);

	memset(s, 0, sizeof s);

	memset(col, 0, sizeof col);

	memset(row, 0, sizeof row);

	memset(ans, 0, sizeof ans);

	cnt = m + 1;

}

inline void insert(int x, int y){

	s[y] ++; row[cnt] = x; col[cnt] = y;

	u[cnt] = y; d[cnt] = d[y];

	d[y] = u[d[y]] = cnt;

	if(h[x] < 0) h[x] = l[cnt] = r[cnt] = cnt;

	else {

		r[cnt] = h[x];

		l[cnt] = l[h[x]];

		l[h[x]] = r[l[h[x]]] = cnt;

	}

	++ cnt;

}

inline void remove(int y){

	r[l[y]] = r[y]; l[r[y]] = l[y];

	for(Rint i = d[y];i != y;i = d[i])

		for(Rint j = r[i];j != i;j = r[j]){

			u[d[j]] = u[j];

			d[u[j]] = d[j];

			s[col[j]] --;

		}

}

inline void resume(int y){

	for(Rint i = u[y];i != y;i = u[i])

		for(Rint j = l[i];j != i;j = l[j]){

			u[d[j]] = d[u[j]] = j;

			s[col[j]] ++;

		}

	r[l[y]] = l[r[y]] = y;

}

inline bool dance(int dep){

	if(!r[0]){

		for(Rint i = 0;i < dep;i ++){

			int x = (ans[i] - 1) / 256 + 1, y = (ans[i] - 1) / 16 % 16 + 1, z = (ans[i] - 1) % 16 + 1;

			a[x][y] = z;

		}

		return true;

	}

	int c = r[0];

	for(Rint i = r[0];i;i = r[i]) if(s[i] < s[c]) c = i;

	remove(c);

	for(Rint i = d[c];i != c;i = d[i]){

		ans[dep] = row[i];

		for(Rint j = r[i];j != i;j = r[j]) remove(col[j]);

		if(dance(dep + 1)) return true;

		for(Rint j = l[i];j != i;j = l[j]) resume(col[j]);

	}

	resume(c);

	return false;

}

int main(){

	freopen("program7.in", "r", stdin);

	freopen("program7.out", "w", stdout);

	for(Rint k = 1;k <= 4;k ++){

		init();

		for(Rint i = 1;i <= 16;i ++)

			for(Rint j = 1;j <= 16;j ++){

				int x;

				while(((x = getchar()) < 'A' || x > 'P') && x != '?');

				a[i][j] = (x == '?') ? 0 : x - 'A' + 1;

				for(Rint k = 1;k <= 16;k ++)

					if(a[i][j] == k || !a[i][j]){

						int id = ((i - 1) * 16 + j - 1) * 16 + k;

						int c1 = (i - 1) * 16 + j, c2 = 256 + (i - 1) * 16 + k, c3 = 512 + (j - 1) * 16 + k,

								c4 = 768 + ((i - 1) / 4 * 4 + (j - 1) / 4) * 16 + k;

						insert(id, c1); insert(id, c2); insert(id, c3); insert(id, c4);

					}

			}

		dance(0);

		for(Rint l = 0;l < k;l ++){

			for(Rint i = 1;i <= 16;i ++)

				for(Rint j = 1;j <= 16;j ++)

					printf("%c", a[i][j] + 'A' - 1);

			putchar('\n');

		}

	}

}

测试点8,9,10：咕了

巴特西

UOJ73 【WC2015】未来程序

最新文章

热门文章