首页 > 其他分享 >AtCoder 好题选做

AtCoder 好题选做

时间：2023-05-11 19:45:53浏览次数：59  
标签：__ AtCoder pbds int gnu tree 好题 include

AtCoder Regular Contest 091 - F - Strange Nim

https://atcoder.jp/contests/arc091/tasks/arc091_d
清北学堂讲的一道题，我艹感觉这结论很难猜啊。
做这种题一定是先写爆搜打表啊，先写了一个博弈论求 SG 函数：
image

然后发现了一个规律：\(\text{SG}(nk,k)=n\)。
还有一个规律：当 \(n < k\) 时，有 \(\text{SG}(n, k) = 0\)。
考虑将 SG 函数值分组：
image

然后我们发现：

\[\text{SG}(n,k)=\text{SG}(n-\left\lfloor\frac{n}{k}\right\rfloor-1,k) \]

现在我们就将 \(\text{SG}\) 函数的表达式算好了，整理有：

\[\text{SG}(n, k) = \begin{cases}0, n < k\\\dfrac{n}{k}, n \bmod k = 0\\\text{SG}(n-\left\lfloor\dfrac{n}{k}\right\rfloor-1,k), n \bmod k \neq 0\end{cases} \]

然后就只会暴力求，就会得到这个，就去看了一眼 Solution，感觉特别牛逼：
image

分析一下，相当于每一次减去 \(\left\lfloor\dfrac{n}{k}\right\rfloor + 1\)，考虑将一样的操作合并，设暂时的 \(\left\lfloor\dfrac{n}{k}\right\rfloor\) 为 \(d\)，那么距离下一个 \(d\) 有 \(n - kd\)，一步为 \(d + 1\)，那么可以合并 \(\left\lceil\dfrac{n - kd}{d + 1}\right\rceil\) 步为一步，这样就可以过了。
时间复杂度？类似于数论分块，毛估估一下是根号级别的，实测 44ms，特别快。
image

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
inline int SG (int x, int k) {
	while (x % k && x >= k) {
		int d = x / k;
		int merge = (x - k * d) / (d + 1);
		if ((x - k * d) % (d + 1)) merge ++;
		x -= merge * (d + 1); 
	}
	return x / k;
}
int n, res;
signed main () {
//	freopen ("AT_arc091_d.txt", "w", stdout);
	n = read ();
	for (int i = 1;i <= n; ++ i) {
		int x = read (), k = read ();
		res ^= SG (x, k);
	}
	if (!res) printf ("Aoki\n");
	else printf ("Takahashi\n");
	return 0;
}

AtCoder Beginner Contest 082 - D - FT Robot

https://atcoder.jp/contests/abc082/tasks/arc087_b
一开始发现我艹，这道题的决策数量这么多，做不了了啊。
然后我想到，决策数量多的，一般都是 DP，然后就想到了做可行性 DP。
然后我们转化一下问题，将第 \(x\) 段，有 \(k\) 个 F 的记作 x 轴（如果 \(x \bmod 2 = 0\) 就是 y 轴）的坐标加减 \(k\)（第一段只能加），然后对于能到达的横坐标和纵坐标分别 DP，就可以了。
因为坐标可能有负数，所以要加上一个足够大（8015）的偏移量。
srds，一交就 WA，查了好久的错误才发现是最后到达的坐标是 \((x,y)\)，不是过程中到达 \((x, y)\) 就可以。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
const int D = 8015;
bool fx[D][2 * D + 100], fy[D][2 * D + 100];
int dx[D][2], dy[D][2], cntx, cnty, tmp, n, goalx, goaly, type, already = 1;
int qwqx[D], qwqy[D], cnt;
char s[D];
signed main () {
	scanf ("%s", s + 1);
	n = strlen (s + 1);
	goalx = read () + D, goaly = read () + D;
	type = 0;
	for (int i = 1;i <= n; ++ i) {
		if (s[i] == 'T') {
			if (already) {
				already = 0;
				if (type == 0) {
					cntx ++;
					dx[cntx][0] = tmp;
					qwqx[cntx] = ++ cnt;
				}
				else {
					cnty ++;
					dy[cnty][0] = tmp;
					qwqy[cnty] = ++ cnt;
				}
			}
			else {
				if (type == 0) {
					cntx ++;
					dx[cntx][0] = tmp;
					dx[cntx][1] = -tmp;
					qwqx[cntx] = ++ cnt;
				}
				else {
					cnty ++;
					dy[cnty][0] = tmp;
					dy[cnty][1] = -tmp;
					qwqy[cnty] = ++ cnt;
				}
			}
			tmp = 0;
			type ^= 1;
		}
		else {
			tmp ++;
		}
	}
	if (already) {
		already = 0;
		if (type == 0) {
			cntx ++;
			dx[cntx][0] = tmp;
			qwqx[cntx] = ++ cnt;
		}
		else {
			cnty ++;
			dy[cnty][0] = tmp;
			qwqy[cnty] = ++ cnt;
		}
	}
	else {
		if (type == 0) {
			cntx ++;
			dx[cntx][0] = tmp;
			dx[cntx][1] = -tmp;
			qwqx[cntx] = ++ cnt;
		}
		else {
			cnty ++;
			dy[cnty][0] = tmp;
			dy[cnty][1] = -tmp;
			qwqy[cnty] = ++ cnt;
		}
	}
	fx[0][D] = true;
	for (int i = 1;i <= cntx; ++ i) {
		for (int j = 0;j <= 2 * D + 99; ++ j) {
			int las1 = j - dx[i][0];
			int las2 = j - dx[i][1];
			if (las1 >= 0 && las1 <= 2 * D + 99) fx[i][j] |= fx[i - 1][las1];
			if (las2 >= 0 && las2 <= 2 * D + 99) fx[i][j] |= fx[i - 1][las2];
		}
	}
	fy[0][D] = true;
	for (int i = 1;i <= cnty; ++ i) {
		for (int j = 0;j <= 2 * D + 99; ++ j) {
			int las1 = j - dy[i][0];
			int las2 = j - dy[i][1];
			if (las1 >= 0 && las1 <= 2 * D + 99) fy[i][j] |= fy[i - 1][las1];
			if (las2 >= 0 && las2 <= 2 * D + 99) fy[i][j] |= fy[i - 1][las2];
		}
	}
	bool jud = false;
	for (int i = cntx;i <= cntx; ++ i) {
		for (int j = cnty;j <= cnty; ++ j) {
			int T = qwqx[i], H = qwqy[j];
			if (!T && !H) jud |= (fx[i][goalx] & fy[j][goaly]);
			else if (T < H && (i == cntx || qwqx[i + 1] > H)) jud |= (fx[i][goalx] & fy[j][goaly]);
			else if (H < T && (j == cnty || qwqy[j + 1] > T)) jud |= (fx[i][goalx] & fy[j][goaly]);
		}
	}
	if (jud) printf ("Yes\n");
	else printf ("No\n");
	return 0;
}

AtCoder Beginner Contest 071 - D - Coloring Dominoes

https://atcoder.jp/contests/abc071/tasks/arc081_b
写在前面：这道题没有做出来，看的 Solution。/ll
我们考虑从左向右填多米诺，分以下四种情况：
1st、
image

右面可以填蓝色 / 绿色，方案数为 \(2\)。
2nd、
image

右面只可以填绿色，方案数为 \(1\)。
3rd、
image

右面可以上面填蓝色，下面填绿色，也可以反过来，方案数为 \(2\)。
4th、
image

这种情况可以上面蓝色，下面红色，也可以上面蓝色，下面绿色，还可以上面绿色，下面红色，总共 \(3\) 种情况。
这样只需要递推即可，将所有可能都乘起来。
注意：如果是开头（第一列），那么第一种情况左面染色的方案数为 \(3\)，第四种方案左面的染色方案的数量为 \(6\)，因为没有前面染色结果的限制。
这道题感觉很好的一道计数题，一开始想的是将相邻的多米诺建图，然后 2-SAT / 容斥等奇奇怪怪的做法，发现都不能做（悲）。
怎样在大分类讨论上做到不重不漏，是个难题。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
const int mod = 1e9 + 7;
char s[2][65];
int ans, n, L;
signed main () {
	n = read ();
	scanf ("%s", s[0] + 1);
	scanf ("%s", s[1] + 1);
	if (s[0][1] == s[1][1]) ans = 3, L = 2;
	else ans = 6, L = 3;
	while (true) {
		if (L > n) break;
		if (s[0][L] == s[1][L] && s[0][L - 1] == s[1][L - 1]) ans = ans * 2 % mod, ++ L;
		else if (s[0][L - 1] == s[1][L - 1] && s[0][L] == s[0][L + 1] && s[1][L] == s[1][L + 1] && L + 1 <= n) {
			L += 2;
			ans = ans * 2 % mod; 
		}
		else if (s[0][L] == s[1][L]) ++ L;
		else ans = ans * 3 % mod, L += 2;
	}
	printf ("%lld\n", ans);
	return 0;
}

AtCoder Regular Contest 059 - E - Children and Candies

https://atcoder.jp/contests/arc059/tasks/arc059_c
这道题看上去很难，但是仔细一想，发现很简单。
考虑 DP，设 \(f_{i,j}\) 表示现在 DP 到第 \(i\) 个人，给前 \(i\) 个人分了 \(j\) 块糖果的答案。
转移的时候要枚举给第 \(i\) 个人分的糖果数 \(c\)，然后转移就很简单了，只需要将贡献乘以以前算出来的 DP 值然后累加即可。

\[f_{i,j} = \sum_{c = 0}^{j}f_{i - 1,j - c} \times \sum_{k = A_i}^{B_i}k^c \]

为什么这样是对的呢，因为乘法分配律，以前算出来的答案其实是一个和，题目要求你算乘积，然后你就将当前的贡献一个一个乘上即可。
upd：一开始暴力转移 TLE 了，仔细一看，发现第二个 sigma 可以用前缀和预处理，然后就砍掉了一个 \(400\) 的复杂度。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
const int mod = 1e9 + 7, N = 405;
int n, c, a[N], b[N], f[N][N], pw[N][N], pre[N][N];
signed main () {
	f[0][0] = 1;
	n = read (), c = read ();
	for (int i = 1;i <= n; ++ i) a[i] = read ();
	for (int i = 1;i <= n; ++ i) b[i] = read ();
	for (int i = 1;i < N; ++ i) {
		pw[i][0] = 1;
		for (int j = 1;j < N; ++ j) pw[i][j] = pw[i][j - 1] * i % mod;
	}
	for (int ind = 0;ind < N; ++ ind) {
		for (int i = 1;i < N; ++ i) pre[i][ind] = (pre[i - 1][ind] + pw[i][ind]) % mod;
	}
	for (int i = 1;i <= n; ++ i) {
		for (int j = 0;j <= c; ++ j) {
			for (int k = 0;k <= j; ++ k) {
				int cur = j - k, sum = (pre[b[i]][cur] - pre[a[i] - 1][cur] + mod) % mod;
				sum = (sum % mod + mod) % mod;
				f[i][j] = (f[i][j] + f[i - 1][k] * sum % mod) % mod;
			}
		}
	}
	printf ("%lld\n", f[n][c]);
	return 0;
}

AtCoder Regular Contest 058 - D - Iroha and a Grid

https://atcoder.jp/contests/arc058/tasks/arc058_b
第一眼：艹，这不就一个 sb DP 吗，秒了秒了。
仔细看了一眼数据范围：wc，这不能用 DP 做了，1e5，悲。
考虑没有限制我们可以随便走，有了限制我们就不能走那边，那么我们找到可以随意走和不能随意走的点的边界，也就是 \((1,b+1), (2,b+1), \dots, (h - a, b + 1)\)，从 \((1, 1)\) 到这些点是可以随便走的，然后就可以随便走到 \((h,w)\) 了。
什么？你说过不了样例？！
哦，原来是算重了，\((1,b+1)\) 可以通过向下一格走到 \((2,b+1)\)，这样就会有很多重复计算。
解决办法也很简单，就是对于 \((1,b+1), (2,b+1), \dots, (h - a - 1, b + 1)\) 的点，钦定下一步必须是向右走，然后就可以随便走，对于 \((h-a,b+1)\)，我们不用担心它算重，因为右下已经没有我们选中的点了，可以随便走。
注：从 \((1,1)\) 走到 \((n,m)\) 的方案数为 \(\dbinom{n+m-2}{n-1}\)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
inline int pow_mod (int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return res;
}
const int mod = 1e9 + 7, N = 3e5 + 5;
int h, w, a, b, chai, ans, fac[N], ifac[N];
inline int C (int n, int m) {
	if (n < 0 || m < 0 || n < m) return 0;
	return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
signed main () {
	fac[0] = ifac[0] = 1;
	for (int i = 1;i < N; ++ i) {
		fac[i] = fac[i - 1] * i % mod;
		ifac[i] = pow_mod (fac[i], mod - 2, mod);
	}
	h = read (), w = read (), a = read (), b = read ();
	for (int i = 1;i <= h - a; ++ i) {
		int x = i, y = b + 1;
		-- x, -- y;
		chai = C (x + y, x);
		++ x, ++ y;
		int tot = 0;
		if (i == h - a) {
			tot = (tot + chai * C (h + w - x - y, h - x) % mod) % mod;
		}
		else {
			y ++;
			if (y <= w) {
				tot = (tot + chai * C (h + w - x - y, h - x) % mod) % mod;
			}
			y --;
		}
		ans = (ans + tot) % mod;
	}
	printf ("%lld\n", ans % mod);
	return 0;
}

Typical DP Contest - J - ボール

https://atcoder.jp/contests/tdpc/tasks/tdpc_ball
这道题想了 1.5h，没有想出来，看了 Solution 才看懂。/ng
状压 + 期望 DP 做题的时候想到了，但就是不知道怎么转移。/ll
然后我们设 \(f_S\) 表示现在打中了坐标在 \(S\) 中的所有点所需要的最优策略的步数，然后只需要转移就好了。

\[f_S = 1 + \frac{1}{3}\sum_{u = x - 1}^{x + 1}f_{S\text{\\}u}+\frac{2}{3}f_S \]

什么？你竟然不会转移，哦确实需要反解一下：

\[\frac{1}{3}f_S = 1 + \frac{1}{3}\sum_{u = x - 1}^{x + 1}f_{S\text{\\}u} \]

\[f_S = \sum_{u = x - 1}^{x + 1}f_{S \text{\\} u} + 3 \]

然后就对于所有的 \(x\) 算出来的值取一个 min 就好了。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
const int N = 20, M = 16;
int n, pos[N], mask, vis[1 << 16], U;
double dp[1 << 16];
inline double query (int S) {
	if (vis[S]) return dp[S];
	vis[S] = 1;
	dp[S] = 1.0 / 0.0;
	for (int i = 0;i <= 15; ++ i) {
		double expect = 1.0;
		vector < int > st;
		st.clear ();
		if (i - 1 >= 0) st.push_back (S & (U ^ (1 << (i - 1))));
		else st.push_back (S & U);
		st.push_back (S & (U ^ (1 << i)));
		st.push_back (S & (U ^ (1 << (i + 1))));
		double cnt = 0;
		for (int j = 0;j < 3; ++ j) {
			if (S == st[j]) continue;
			expect += query (st[j]) / 3.0, cnt += 1.0;
		}
		expect *= 3.0;
		expect /= cnt;
		dp[S] = dp[S] > expect ? expect : dp[S];
	}
	return dp[S];
}
signed main () {
	U = (1 << 29) - 1;
	n = read ();
	vis[0] = 1, dp[0] = 0.0; 
	for (int i = 1;i <= n; ++ i) pos[i] = read (), mask |= (1 << pos[i]);
	printf ("%.7lf\n", query (mask));	
	return 0;
}

Typical DP Contest - N - 木

https://atcoder.jp/contests/tdpc/tasks/tdpc_tree
这道题，想了 40min 没有想出来，又看了 Solution 才看出来。
我们钦定第一条选的边 \((u,v)\)，然后就是给 \(u\) 的子树和 \(v\) 的子树连边，设 \(f_k\) 表示以 \(k\) 为根的子树连边方案，\(edge_k\) 表示以 \(k\) 为根的子树内的边的数量，\(cur\) 表示当前已经有的边的数量，那么当前节点为 \(u\)，对于其一个儿子 \(v\)，有以下转移：

\[cur + edge_{v} + 1 \to cur \]

\[f_u \times f_v \times \dbinom{cur}{edge_v + 1} \to f_u \]

注解：\(edge_v\) 要再加上 \(1\) 是因为还有 \((u,v)\) 这一条边。
然后很快的写完了代码，交上去 WA 了。
查了半天错，最后发现是因为这个：
image

发现是计算过程中爆 long long 了（悲）。
然后就调了 25min，，。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
const int N = 1005, mod = 1e9 + 7;
int n, dp[N], vis[N], ced[N], ed[N][2], combine[N][N], fac[N], ifac[N];
inline int pow_mod (int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		b >>= 1, a = a * a % p;
	}
	return res;
}
vector < int > tr[N];
inline void prework (int u) {
	vis[u] = 1;
	for (int v : tr[u]) {
		if (vis[v]) continue;
		prework (v);
		ced[u] += ced[v] + 1;
	}
}
inline void DP (int u) {
	int nows = 0;
	dp[u] = 1;
	vis[u] = 1;
	for (int v : tr[u]) {
		if (vis[v]) continue;
		DP (v);
		nows += ced[v] + 1;
		dp[u] = dp[u] * combine[nows][ced[v] + 1] % mod * dp[v] % mod;
	}
}
signed main () {
	n = read ();
	for (int i = 1;i < n; ++ i) {
		ed[i][0] = read (), ed[i][1] = read ();
		tr[ed[i][0]].push_back (ed[i][1]);
		tr[ed[i][1]].push_back (ed[i][0]);
	}
	fac[0] = ifac[0] = 1;
	for (int i = 1;i < N; ++ i) {
		fac[i] = fac[i - 1] * i % mod;
		ifac[i] = pow_mod (fac[i], mod - 2, mod);
	}
	for (int i = 0;i < N; ++ i) {
		for (int j = 0;j <= i; ++ j) {
			combine[i][j] = fac[i] * ifac[j] % mod * ifac[i - j] % mod;
		}
	}
	int ans = 0;
	for (int i = 1;i < n; ++ i) {
		int u = ed[i][0], v = ed[i][1];
		for (int j = 1;j <= n; ++ j) vis[j] = ced[j] = 0, dp[j] = 0;
		vis[u] = vis[v] = 1;
		prework (u), prework (v);
		for (int j = 1;j <= n; ++ j) vis[j] = 0;
		vis[u] = vis[v] = 1;
		DP (u), DP (v);
		int cur = dp[u] * dp[v] % mod * combine[ced[u] + ced[v]][ced[u]] % mod;
		ans = (ans + cur) % mod;
	}
	printf ("%lld\n", ans);
	return 0;
}

AtCoder Beginner Contest 154 - F - Many Many Paths

https://atcoder.jp/contests/abc154/tasks/abc154_f
写在前面：这道题整整想 + 写了 70min，感觉收获满满 qwq。
我们发现一个重要的性质，就是按照 DP 的思路：

\[f(x,y) = f(x - 1,y) + f(x,y - 1) \]

然后我们就可以把它转化到平面上，将 \(f(x, y)\) 的值抽象成平面上 \((x,y)\) 的点权：
比如：
image

红点的点权相当于两个橙点的点权之和。
然后一开始想到了将所有点的点权都压到一个点或一排点去，事实上这是很难做的，就没有做出来。
然后我想，可不可以先将点权不那么着急的分解成两个点权相加，只将一个点分解？
然后就有了这个式子：\(f(x,y) = f(x - 1, y) + f(x - 1, y - 1) + \dots + f(x - 1, 0)\)。
然后就可以用 \(O(c_2)\) 的时间内算出 \(\displaystyle \sum_{i = 0}^{r_2}\sum_{j = 0}^{c_2} f(i, j)\) 了，然后我们只需要将这个矩形容斥一下即可，如果 \(r_2 = 0\) 或者 \(c_2 = 0\) 也不用特判，因为这是 trival 的。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
#define int long long
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline int read () {
	int x = 0, f = 0;
	char c = getchar ();
	for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
	for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
	return !f ? x : -x;
}
inline int pow_mod (int a, int b, int p) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		b >>= 1;
		a = a * a % p;
	}
	return res;
}
const int mod = 1e9 + 7, N = 3e6 + 5;
int fac[N], ifac[N], lx, ly, rx, ry, dd[N];
inline int C (int n, int m) {
	if (n < 0 || m < 0 || n - m < 0) return 0;
	return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
inline int calc (int x, int y) {
	int tot = 0;
	for (int i = 1;i <= x + 1; ++ i) tot = (tot + C (i + y, y)) % mod;
	return tot;
}
signed main () {
	fac[0] = ifac[0] = 1;
	for (int i = 1;i < N; ++ i) {
		fac[i] = fac[i - 1] * i % mod;
		ifac[i] = pow_mod (fac[i], mod - 2, mod);
	}
	int ans = 0;
	lx = read (), ly = read (), rx = read (), ry = read ();
	ans += calc (rx, ry);
	ans -= calc (lx - 1, ry);
	ans -= calc (rx, ly - 1);
	ans += calc (lx - 1, ly - 1);
	ans = (ans % mod + mod) % mod;
	printf ("%lld\n", ans); 
	return 0;
}

wc 我做了 1h 的题竟然只是个 1775 分的题？！我裂开来！

标签：__,AtCoder,pbds,int,gnu,tree,好题,include
From： https://www.cnblogs.com/RB16B/p/17392022.html

相关文章

  • AtCoder Beginner Contest 298 题解
    题面：https://atcoder.jp/contests/abc298/tasks_printA-JobInterview直接模拟即可。#include<bits/stdc++.h>#include<ext/pb_ds/assoc_container.hpp>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/hash_policy.hpp>usingnamespace......
  • AtCoder DP系列刷题记录
    直面自己的弱点。AFrog1简单线性\(\text{dp}\)，令\(dp_i\)为跳到第\(i\)块石头的最小花费，易得：\[dp_i+=\min(|a_i-a_{i-1}|,|a_i-a_{i-2}|)\]BFrog2很快就写完了，但是一直调了十分钟，耻辱啊。如果反着跳，第\(i\)根木桩只能从第\(i+1\)或\(i+2\)木桩上跳到，则有：\[d......
  • AtCoder Beginner Contest 234 Ex Enumerate Pairs
    洛谷传送门AtCoder传送门把每个点分到\((\left\lfloor\frac{x}{K}\right\rfloor,\left\lfloor\frac{y}{K}\right\rfloor)\)的正方形内，枚举相邻正方形，计入答案。正确性显然。复杂度证明就是所有每个正方形内距离为\(K\)的点对下界为\(\Omega(n^2)\)。考虑分成四个边长为......
  • AtCoder Beginner Contest 221 F Diameter set
    洛谷传送门AtCoder传送门显然，选出的每两个点都要组成一条直径。还是显然，每条直径的重合部分只可能是一个点或一条边。简单证一下，没有重合显然不可能，重合超过一个点或一条边，直径会更长。进一步发现，设直径点数为\(x\)，如果\(x\nmid2\)，重合部分是一个点，否则重合部分是一条边......
  • AtCoder Beginner Contest 206（Sponsored by Panasonic）（E，F）
    AtCoderBeginnerContest206（SponsoredbyPanasonic）（E，F）E（容斥，gcd)E这个题大意就是给出一个\(l\)和一个\(r\),寻找满足以下条件的一对数\((x,y)\)的数量\(gcd(x,y)!=1\)\(gcd!=x\)并且\(gcd!=y\)(从这一句我们可以知道\(x\)不可能被\(y\)整除)那么我们可以设\(x\)是\(t\)的倍......
  • AtCoder Beginner Contest 217 G Groups
    洛谷传送门AtCoder传送门不妨钦定组之间的顺序是最小值越小的组越靠前，这样可以给每个组按顺序编号。设\(f_{i,j}\)为考虑了模\(m\)后\(<i\)的数，目前有\(j\)个非空组的方案数。转移就是枚举模\(m=i-1\)的数新开了\(k\)个组，设\(\len\)的数中模\(m=i-1......
  • [AtCoder-AT_ABC070C]题解(C++)
    PartIPreface原题目(Luogu)原题目(AtCoder)PartIISketch给定一个正整数\(N(1\leqN\leq100)\)，表示时钟数量。接下来\(N\)行，每行一个正整数\(T_i(1\leqT_i\leq10^{18})\)，表示每个时钟旋转\(T_i\)秒后还会回到原来的地方。求出在多少秒之后，所有时钟还会同时......
  • [AtCoder-AT_ABC070_A]题解(C++)
    PartIPreface原题目(Luogu)原题目(AtCoder)PartIISketch给定一个正整数\(n(100\leqn\leq999)\)。求\(n\)是否是一个回文数，是输出\(\texttt{Yes}\)，不是输出\(\texttt{No}\)。PartIIIAnalysisSolve1如果仔细观察的话，应该都能发现，\(n\)一定是一个三位数。......
  • AtCoder Beginner Contest 209（D，E）
    AtCoderBeginnerContest209（D，E）D(树,lca)D这个题给出\(n\)个点，\(n-1\)条边，有两个人，一个人在\(c\)点，一个人在\(d\)点，两人以相同的速度朝着对方走来（并且都是按照最短路的走法），问这两个人相遇是在点上，还是在路上这一题意很好知道，就是判断这两点之间的最短距离的奇偶性然后我就一......
  • Atcoder Grand Contest 046 D - Secret Passage
    思路挺自然的一道agc。首先发现删除完字符后的状态可以用一个三元组\((i,j,k)\)表示，其中\(i\)表示删除完之后只剩\([i+1,n]\)的后缀，\(j\)表示可以在后面插入\(j\)个\(0\)，\(k\)表示可以在后面插入\(k\)个\(1\)，显然不同的三元组能够得到的串是不同的，而一组三元组可......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99