题意

给定 $n$ 元高次方程

$$\sum_{i=1}^na_ix_i^{p_i}=0 $$

求整数解数。

$1\leq n\leq6,1\leq m\leq150$ 。

题解

一眼折半。用 pbds。

代码

要开 __int128，这里没开。

using namespace __gnu_pbds;

const int N = 10, M = 155;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int a[N], p[N];
	int sum, ans;
	gp_hash_table<int, int> hs[2];
	int qpow (int a, int b) {
		int ans = 1;
		for (; b; b >>= 1, a = a * a)
			if (b & 1) ans = ans * a;
		return ans;
	}
	void dfs (int x, int n, int op) {
		if (x > n) {
			if (!hs[op][sum]) hs[op][sum] = 1; else hs[op][sum]++;
			return;
		}
		for (int i = 1; i <= m; ++i) {
			int tmp = qpow(i, p[x]) * a[x];
			sum += tmp;
			dfs (x + 1, n, op);
			sum -= tmp;
		}
	}
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i <= n; i++) a[i] = Read(), p[i] = Read();
		dfs (1, n / 2, 0);
		dfs (n / 2 + 1, n, 1);
		for (auto ec: hs[0]) {
			int k = ec.first, v = ec.second;
			ans += hs[1][-k] * v;
		}
		printf ("%d\n", ans);
		return 0;
	}
}

int main () {
	freopen("equation.in", "r", stdin);
	freopen("equation.out", "w", stdout);
	Main::main();
	return 0;
}