1. 给出n条水平直线和m条竖直直线，k个石头，石头只能放在直线交点，问最多能组成多少边平行于直线的矩形

$n, m \leq 30000, k \leq n \times m$

【题解】暴力即可。注意边界。

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>
# include <math.h>
# include <iostream>

using namespace std;

int n, m, k;
long long ans = 0;

inline long long get(int i, int j) {
	return (long long)i*(i-1)/2 * (long long)j*(j-1)/2;
}

int main() {
	freopen("rectangle.in", "r", stdin);
	freopen("rectangle.out", "w", stdout);
	
	int i;
	
	scanf("%d%d%d", &n, &m, &k);
	
	if(n>m) swap(n, m);
	
	int s = sqrt(k);
	if(s*s == k) i=s;
	else i=s+1;
	
	for (; i>=2; --i) {
		int j=k/i;
		if(min(i, j) > n || max(i, j) > m) continue;
		if(k%i == 0) {
			long long cur = get(i, j);
			if(cur > ans) ans = cur;
		} else {
			int res = k-i*j;
			long long cur=0;
//			cout << "i=" << i << endl;
			if (i == n && j == m) continue;
//			cout << "i=" << i << " j=" << j << endl;
			if (min(i, j+1) <= n && max(i, j+1) <= m) {
				int a = i, b = j+1, c = res;
//				printf("a=%d, b=%d, c=%d\n", a, b, c);
				cur = get(b, c) + get(a, b-1) - get(b-1, c);
//				printf("%lld %lld %lld\n", get(b, c), get(a, b-1), get(b-1, c));
				if(cur > ans) ans = cur;
			}
		}
	}
	
	cout << ans << endl;
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

2. 求斐波那契数列的第x~y项之和。T组询问。对$10^4$取模。

$x, y \leq 2^{31}-1$

【题解】

方法一：构造矩阵乘法，加入前缀和$s_{i-1}$和$s_{i-2}$两维转移。复杂度$O(4^{3}Tlogy)$

方法二：构造矩阵乘法，由于$s_{i} = f_{i+2} - 1$即可矩阵乘$f$，从而推出。复杂度$O(2^{3}Tlogy)$

方法三：由于对$10^4$取模，尾数每$1.5\times10^{4}$是一个循环，从而较快算出前缀和。复杂度$O(15000+T)$

我用的是方法一

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>
# include <iostream>

using namespace std;

struct matrix {
	int n, m, a[20][20];
} t1, t2, f1, f2, tem1, tem2;
const int MOD=1e4;

inline void add(int &x, int y) {
	y = y % MOD;
	x = (x+y) % MOD;
}

inline struct matrix mul(struct matrix a, struct matrix b) {
	struct matrix c;
	memset(c.a, 0, sizeof(c.a));
	c.n=a.n, c.m=b.m;
	for (int i=1; i<=c.n; ++i)
		for (int j=1; j<=c.m; ++j) 
			for (int k=1; k<=a.m; ++k) 
				add(c.a[i][j], a.a[i][k] * b.a[k][j]);
	return c;
}

inline struct matrix matrixpow(struct matrix a, int b) {
	struct matrix ret;
	memset(ret.a, 0, sizeof(ret.a));
	ret.n = 4, ret.m = 4;
	ret.a[1][1] = ret.a[2][2] = ret.a[3][3] = ret.a[4][4] = 1;
	while(b) {
		if(b&1) ret = mul(ret, a);
		a = mul(a, a);
		b>>=1; 
	}
	return ret;
}

inline void outputmatrix(matrix a) {
	for (int i=1; i<=a.n; ++i, printf("\n"))
		for (int j=1; j<=a.m; ++j) printf("%d ", a.a[i][j]);
}

int main() {
	freopen("fibonacci.in", "r", stdin);
	freopen("fibonacci.out", "w", stdout);
	int T;
	scanf("%d", &T);
	while(T--) {
		t1.n = t1.m = 4;
		memset(t1.a, 0, sizeof(t1.a));
		t1.a[1][1] = t1.a[1][2] = t1.a[2][1] = t1.a[3][1] = t1.a[3][3] = t1.a[4][3] = 1;
		t2 = t1;
		f1.n = 4, f1.m = 1;
		memset(f1.a, 0, sizeof(f1.a));
		f1.a[1][1] = f1.a[3][1] = 1;
		f2 = f1;
		// outputmatrix(f1), outputmatrix(t1);
		int x, y;
		scanf("%d%d", &x, &y);
		tem1 = matrixpow(t1, x-1);	
		tem2 = matrixpow(t2, y);
		f1 = mul(tem1, f1);
		f2 = mul(tem2, f2);
		printf("%d\n", (f2.a[3][1] - f1.a[3][1] + MOD) % MOD);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

3. 给出一张$n$个点$m$条边的无向连通图，求删去边使他成为一棵树后，1号点到其他点最短距离没变的方案数。

$ n \leq 1000, m \leq \frac{n(n-1)}{2}$

【题解】

我用的是spfa，和下面题解写的差不多。

100%：

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <algorithm>
# include <iostream>
# include <queue>
using namespace std;

int n, m;
bool vis[1010];
int we[1010][1010], d[1010];
int head[1010], next[2000020], to[2000020], w[2000020], tot=0;
const long long mod = 2147483647;
long long ans=1;
struct node {
	int id, d;
}a[1010];
queue<int> q;

inline bool cmp(node a, node b) {
	return a.d < b.d;
}

inline void add(int u, int v, int tw) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	w[tot]=tw;
	we[u][v]=tw;
}

int main() {
	freopen("treecount.in", "r", stdin);
	freopen("treecount.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i) for (int j=1; j<=n; ++j) we[i][j] = 1000000000;
	for (int i=1, u, v, tw; i<=m; ++i) {
		scanf("%d%d%d", &u, &v, &tw);
		add(u, v, tw);
		add(v, u, tw);
	}
	q.push(1); vis[1]=1, d[1]=0;
	for (int i=2; i<=n; ++i) d[i] = 1000000000;
	while(!q.empty()) {
		int top=q.front(); q.pop(); vis[top]=0;
		for (int i=head[top]; i; i=next[i]) 
			if(d[to[i]] > d[top] + w[i]) {
				d[to[i]] = d[top] + w[i];
				if(!vis[to[i]]) {
					vis[to[i]] = 1;
					q.push(to[i]);
				}
			}
	}
	for (int i=1; i<=n; ++i) a[i].id=i, a[i].d=d[i];
	sort(a+1, a+n+1, cmp);
	for (int i=2; i<=n; ++i) {
		long long cur=0;
		for (int j=1; j<i; ++j) 
			if(a[i].d == a[j].d + we[a[i].id][a[j].id]) ++cur;
		ans = ans * cur % mod;
	}
	cout << ans << endl;
	fclose(stdin);
	fclose(stdout);
	return 0;
}