Basketball1

Divide the array into two halves, find some numbers in each half, and find the number of schemes that make a group of XOR and sum on the left equal to a group of and and and sum on the right

I didn't see it split in half. In fact, I thought of the positive solution at the beginning, but I couldn't PASS the cross selection, so PASS lost the positive solution

Let \ (f_{i, j, 0} \) represent the number of previous \ (I \), the XOR sum is \ (j \), and the number of schemes of \ (I \) in the set

\(f_{i, j, 1} \) represents the number of schemes after \ (i \) (including \ (i \)) and the sum is equal to \ (j \), and \ (i \) is in the set

Auxiliary array \ (g_j \) records (before / after) suffix sum, which changes as appropriate

Count straight on the left and backwards on the right

When counting the answers, enumerate the breakpoints and multiply the number of schemes whose left and right XOR / and sum are equal to the same number. This breakpoint is the answer to this value, which can be accumulated

#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
using namespace std;
const int MOD(1000000007);
inline unsigned int RD() {
	register unsigned int rdtp(0);
	register char rdch(getchar());
	while ((rdch > '9') || (rdch < '0')) {
		rdch = getchar();
	}
	while ((rdch <= '9') && (rdch >= '0')) {
		rdtp *= 10;
		rdtp += rdch - '0'; 
		rdch = getchar();
	}
	return rdtp;
}
unsigned int n, a[1005], g[1050]/*Auxiliary array*/, f[1005][1050][2];
unsigned long long Ans(0);
int main() {
	freopen("basketball1.in","r",stdin);
	freopen("basketball1.out","w",stdout);
	n = RD();
	if(!n) {
		printf("0\n");
		return 0;
	}
	memset(f, 0, sizeof(f));
	memset(g, 0, sizeof(g));
	for (register unsigned int i(1); i <= n; ++i) {
		a[i] = RD();
	}
	for (register unsigned int i(1); i <= n; ++i) {
		for(register unsigned int j(0); j < 1024; ++j) {
			f[i][j ^ a[i]][0] += g[j];
			f[i][j ^ a[i]][0] %= MOD;
		}
		++f[i][a[i]][0];
		for (register unsigned int j(0); j < 1024; ++j) {
			g[j] += f[i][j][0];
			g[j] %= MOD;
		}
	}
	memset(g, 0, sizeof(g));
	for (register unsigned int i(n); i >= 1; --i) {
		for(register unsigned int j(0); j < 1024; ++j) {
			f[i][j & a[i]][1] += g[j];
			f[i][j & a[i]][1] %= MOD;
		}
		++f[i][a[i]][1];
		for (register unsigned int j(0); j < 1024; ++j) {
			g[j] += f[i][j][1];
			g[j] %= MOD;
		}
	}
	memset(g, 0, sizeof(g));
	for(register unsigned int i(1); i < n; ++i) {
		for(register unsigned int j(0); j < 1024; ++j) {
			g[j] += f[i][j][0];
			g[j] %= MOD;
			Ans += (long long)g[j] * f[i + 1][j][1];
			Ans %= MOD;
		}
	}
	printf("%llu", Ans);
	return 0; 
}

Basketball2

Give the number of people \ (n \), upper bound of weight \ (l \), demand weight and \ (k \) Find the number of weight schemes (not the number of selected schemes) that can take out the weight sum of \ (k \)

\(n, k \leq 20\)

Permutation and combination and other DP algorithms seem to involve the problem of repeated statistics

\(dp_{i, state} \) represents the first \ (I \) bit, \ (State \) represents the weight and the total number of schemes that can be obtained

Enumerate the \ (i + 1 \) th fetched number \ (x \)

If the fetched number is greater than \ (k \), it is equivalent to the patching number, and direct statistics

\(O(n^22^n) \), but there are many pressing waste states. Cut off the waste state to AC (otherwise \ (80 \))

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int MOD(1000000007);
inline unsigned int RD() {
	register unsigned int rdtp(0);
	register char rdch(getchar());
	while ((rdch > '9') || (rdch < '0')) {
		rdch = getchar();
	}
	while ((rdch <= '9') && (rdch >= '0')) {
		rdtp *= 10;
		rdtp += rdch - '0'; 
		rdch = getchar();	
	}
	return rdtp;
}
unsigned int N, n, K, k, l, f[1050000][25], tmp;
unsigned long long Ans(0);
int main() {
	freopen("basketball2.in","r",stdin);
	freopen("basketball2.out","w",stdout);
	n = RD();
	k = RD();
	l = RD();
	K = min(k, l);
	N = (1 << k) - 1;
	memset(f, 0, sizeof(f));
	if(!l) {
			if(k){
				printf("0\n");
				return 0;
			}
		printf("1\n");
		return 0;
	}
	f[0][0] = 1;
	for (register unsigned int i(1); i <= n; ++i) {
		for (register unsigned int m(0); m <= N; ++m) {
			if(f[m][i - 1]) {
				for (register unsigned int j(0); j <= K; ++j) {
					tmp = (m/*It was possible*/ | (m << j/*Add j new ones*/) | (1 << (j - 1))/*Select only the i-th person*/) & ((1 << k) - 1)/*Prevent overflow and control it within the required range*/;
					f[tmp][i] += f[m][i - 1];
					f[tmp][i] %= MOD;
				}
			}
		}
		if(l > k) {
			for (register unsigned int m(0); m <= N; ++m) {
				f[m][i] += ((long long)f[m][i - 1] * (l - k)) % MOD;//Numbers greater than k are useless for counting 
				f[m][i] %= MOD;
			}
		}
	}
	for(register unsigned int i(1 << (k - 1)); i <= N; ++i) {
		Ans += f[i][n];
	}
	Ans %= MOD; 
	printf("%llu\n", Ans);
	return 0; 
}

Maze

A \ (n * n \) chessboard

• #It's a wall. You can't go
• S is a problem. It takes \ (1 \) more time and only needs to be solved once
• K is the starting point
• T is the end point
• The number x is the \ (x \) key. Take it one by one from \ (1 \)
• It's an ordinary grid

Four connections between grids take \ (1 \) time to move each time. Find the shortest time to get all keys from \ (K \) and reach \ (T \)

\(0 < n \leq 100, 0 \leq m \leq 9, S_{num} \leq 5\)

Since there are few S in this question, enumerate whether each S is done or not (if not, it is temporarily set as #), and then directly BFS

Take the keys in sequence, add one dimension to indicate the keys already obtained, and turn the chessboard into three dimensions. When there are keys, there are two branches. Take or not take them. If you don't take them, you will continue to walk on this floor and go to the next floor

Set \ (f_{i, j, k} \) as the time when the key \ (k \) is obtained at point \ ((i, j) \), and join the team if it is updated, otherwise it will not join the team

#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int MOD(1000000007);
inline unsigned int RD() {
	register unsigned int rdtp(0);
	register char rdch(getchar());
	while ((rdch > '9') || (rdch < '0')) {
		rdch = getchar();
	}
	while ((rdch <= '9') && (rdch >= '0')) {
		rdtp *= 10;
		rdtp += rdch - '0'; 
		rdch = getchar();
	}
	return rdtp;
}
struct Pnt {
	unsigned int x, y, key;
	Pnt (unsigned int a = 0, unsigned int b = 0, unsigned int c = 0) {
		x = a;
		y = b;
		key = c; 
	}
};
queue<Pnt> Q;
//bool b[105][105];
unsigned int Cnt(0), sx, sy, tx, ty, S[7][2], m, n, f[105][105][10]/*f[i][j][k]:Get the k-th key in the shortest time of I and J*/, Ans(0x3f3f3f3f);
char s[105], a[105][105];
void Udt (const Pnt &x, const Pnt &y) {
	if (y.key + 1 == x.key) {
		if (f[x.x][x.y][x.key] > f[y.x][y.y][y.key] + 1) {//Pick
			f[x.x][x.y][x.key] = f[y.x][y.y][y.key] + 1;
			Q.push(x);
		}
	}
	if (f[x.x][x.y][y.key] > f[y.x][y.y][y.key] + 1) {//Not Pick
		f[x.x][x.y][y.key] = f[y.x][y.y][y.key] + 1;
		Q.push(Pnt(x.x, x.y, y.key));
	}
	return;
}
inline void Inst (Pnt x, const Pnt &y) {
	if (a[x.x][x.y] == 0x7f) {
		return;
	}
	x.key = (unsigned int)a[x.x][x.y];
	if(!x.key) {
		x.key = y.key;
	}
	Udt(x, y);
	return;
} 
void BFS() {
	Pnt x;
	Q.push(Pnt(sx, sy, 0));
	while (Q.size()) {
		x = Q.front();
		if (x.x - 1) {
			Inst(Pnt(x.x - 1, x.y, 0), x);
		}
		if (x.x + 1 <= n) {
			Inst(Pnt(x.x + 1, x.y, 0), x);
		}
		if (x.y - 1) {
			Inst(Pnt(x.x, x.y - 1, 0), x);
		}
		if (x.y + 1 <= n) {
			Inst(Pnt(x.x, x.y + 1, 0), x);
		}
		Q.pop();
	}
	return;
}
void DoS(unsigned int Dep, unsigned int Chost) {
	if(Dep > Cnt) {//After enumeration, let's go 
		memset(f, 0x3f, sizeof(f));
		f[sx][sy][0] = Chost;
		BFS();
		Ans = min(f[tx][ty][m], Ans);
		return; 
	}
	a[S[Dep][0]][S[Dep][1]] = 0x7f; 
	DoS(Dep + 1, Chost);
	a[S[Dep][0]][S[Dep][1]] = 0;
	DoS(Dep + 1, Chost + 1);
	return;
} 
int main() {
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	n = RD();
	m = RD();
	if(!n) {
		printf("0\n");
		return 0;
	}
	memset(a, 0, sizeof(a));
	for (register unsigned int i(1); i <= n; ++i) {
		gets(s);
		for (register unsigned int j(1); j <= n; ++j) {
			switch(s[j - 1]) {
				case '#':{
					a[i][j] = 0x7f;
					break;
				}
				case '.': {
					break;
				}
				case 'K': {
					sx = i;
					sy = j;
					break;
				}
				case 'S': {
					S[++Cnt][0] = i;
					S[Cnt][1] = j;
					break;
				}
				case 'T': {
					tx = i;
					ty = j;
					break;
				}
				default: {
					a[i][j] = s[j - 1] - '0';
					break;
				} 
			}
		}
	}
	memset(f, 0x3f, sizeof(f));
	DoS(1, 0);
	if(Ans >= 1000000000) {
		printf("impossible\n");
		return 0;
	}
	printf("%u\n", Ans);
	return 0; 
}