Product Tuples

正解是 fft，这里我直接暴力 DP 做掉了这个题。注意的是暴力做法的话用long long被卡掉了，只能全程用int做模运算。

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
struct Mod
{
	const ll M, SM;
	Mod(ll M) : M(M), SM(sqrt(M) + 0.5) {}
	ll qadd(ll &a, ll b) const { return a += b, a >= M ? a -= M : a; } //假如a+b<2*M，就不必取模了，取模运算耗时很高
	ll add(ll a, ll b) const { return qadd(a = (a + b) % M, M); }	  //考虑a和b不在同余系内甚至为负数的情况
	ll mul(ll a, long long b) const { return a * b % M; }
	ll inv(ll a) const { return pow(a, M - 2); } //要求M为素数，否则return pow(a, phi(M) - 1);
	ll pow(ll a, ll b) const
	{
		ll r = 1;
		/*
		if (b < 0)
			b = -b, a = inv(a);
		*/
		for (a = add(a, M); b; b >>= 1, a = mul(a, a))
			if (b & 1)
				r = mul(r, a);
		return r;
	}
	/*
	ll mul(ll a, ll b) const { return add(a * b, -M * ll((long double)a / M * b)); } //long double 有效位数16~18位，模数过大时慎用！
	ll mul(ll a, ll b) const //Head算法，无循环快速计算同余乘法，根据a*b是否爆ll替换a*b%M，需要a<M且b<M，可以调用时手动取模
	{
		ll c = a / SM, d = b / SM;
		a %= SM, b %= SM;
		ll e = add(add(a * d, b * c), c * d / SM * (SM * SM - M));
		return add(add(a * b, e % SM * SM), add(c * d % SM, e / SM) * (SM * SM - M));
	}
  ll mul(ll a, ll b) const //龟速乘
	{
		ll r = 0;
		for (a %= M; b; b >>= 1, qadd(a, a))
			if (b & 1)
				qadd(r, a);
		return r;
	}
	ll inv(ll a) const //模m下a的乘法逆元，不存在返回-1（m为素数时a不为0必有逆元）
	{
		ll x, y, d = gcd(a, M, x, y);
		return d == 1 ? add(x, M) : -1;
	}
	vector<ll> sol(ll a, ll b) const //解同余方程，返回ax=b(mod M)循环节内所有解
	{
		vector<ll> ans;
		ll x, y, d = gcd(a, M, x, y);
		if (b % d)
			return ans;
		ans.push_back(mul((b / d) % (M / d), x));
		for (ll i = 1; i < d; ++i)
			ans.push_back(add(ans.back(), M / d));
		return ans;
	}
	ll log(ll a, ll b) const
	{
		unordered_map<ll, ll> x;
		for (ll i = 0, e = 1; i <= SM; ++i, e = mul(e, a))
			if (!x.count(e))
				x[e] = i;
		for (ll i = 0, v = inv(pow(a, SM)); i <= SM; ++i, b = mul(b, v))
			if (x.count(b))
				return i * SM + x[b];
		return -1;
	}
	*/
} M(998244353);
int n, k, q, o, x, l, r, d;
int main()
{
	scanf("%d%d", &n, &k);
	vector<int> aa(n);
	for (int i = 0; i < n; ++i)
		scanf("%d", &aa[i]);
	for (scanf("%d", &q); q--;)
	{
		vector<int> a = aa, f(k + 1, 0);
		scanf("%d%d%d", &o, &x, &l);
		if (o == 1)
			scanf("%d", &a[l - 1]);
		else
		{
			scanf("%d%d", &r, &d);
			for (int i = l - 1; i < r; ++i)
				a[i] += d;
		}
		for (int i = 0; i < n; ++i)
			a[i] = M.add(x, -a[i]);
		f[0] = 1;
		for (int i = 0; i < n; ++i)
			for (int j = min(i + 1, k), jb = max(1, k - (n - i - 1)); j >= jb; --j)
				M.qadd(f[j], M.mul(f[j - 1], a[i]));
		printf("%d\n", f[k]);
	}
}

Workout plan

队友做的这题，看起用了线段树。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = 1e5 + 10, INF = 1e9 + 10;
int n, k, add;
int a[maxn], mon[maxn];
LL ans = 0;
struct node
{
	int num, loc;
} tree[4 * maxn];

void build(int root, int L, int R)
{
	if (L == R)
	{
		tree[root].num = mon[L];
		tree[root].loc = L;
		return;
	}
	int mid = (L + R) / 2;
	int Lson = root * 2, Rson = root * 2 + 1;
	build(Lson, L, mid);
	build(Rson, mid + 1, R);
	if (tree[Lson].num < tree[Rson].num)
	{
		tree[root].num = tree[Lson].num;
		tree[root].loc = tree[Lson].loc;
	}
	else
	{
		tree[root].num = tree[Rson].num;
		tree[root].loc = tree[Rson].loc;
	}
}

void upnode(int root, int L, int R, int x, int val)
{
	if (L == x && x == R)
	{
		tree[root].num = val;
		return;
	}
	if (x < L || R < x)
		return;
	int mid = (L + R) / 2;
	int Lson = root * 2, Rson = root * 2 + 1;
	upnode(Lson, L, mid, x, val);
	upnode(Rson, mid + 1, R, x, val);
	if (tree[Lson].num < tree[Rson].num)
	{
		tree[root].num = tree[Lson].num;
		tree[root].loc = tree[Lson].loc;
	}
	else
	{
		tree[root].num = tree[Rson].num;
		tree[root].loc = tree[Rson].loc;
	}
}

node query(int root, int L, int R, int i, int j)
{
	node now;
	now.num = INF;
	now.loc = 0;
	if (i <= L && R <= j)
		return tree[root];
	if (j < L || R < i)
		return now;

	int mid = (L + R) / 2;
	int Lson = root * 2, Rson = root * 2 + 1;
	node now1 = query(Lson, L, mid, i, j);
	node now2 = query(Rson, mid + 1, R, i, j);
	if (now1.num < now2.num)
		return now1;
	else
		return now2;
}

int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	scanf("%d", &add);
	for (int i = 1; i <= n; i++)
		scanf("%d", &mon[i]);
	build(1, 1, n);

	bool ok = true;
	for (int i = 1; i <= n; i++)
	{
		while (k < a[i])
		{
			node res = query(1, 1, n, 1, i);
			if (res.num == INF)
			{
				ok = false;
				break;
			}
			upnode(1, 1, n, res.loc, INF);
			k += add;
			ans += (LL)res.num;
		}
		if (!ok)
			break;
	}
	if (ok)
		printf("%lld\n", ans);
	else
		printf("-1\n");

	return 0;
}

The Light Square

2sat。