BreakFast:2021HDU暑期多校训练营1 - Revision history

BreakFast: /* bitset 优化 */ update D

2021-07-30T07:51:09Z

bitset 优化: update D

← Older revision		Revision as of 07:51, 30 July 2021
Line 379:		Line 379:
	return 0;		return 0;
	}</syntaxhighlight>		}</syntaxhighlight>
	[https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop]
			== [https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop] ==

			=== 题目大意 ===

			<math display="inline">T</math> 组输入，每组给 <math display="inline">n</math> 和 <math display="inline">k</math>.

			有 <math display="inline">n</math> 个物品，价值分别为 <math display="inline">a[1], a[2], \cdots, a[n]</math>，每件物品有无穷多件.

			求拼凑出总价值为 <math display="inline">k</math> 的方案数.

			<math display="inline">1 \leq T \leq 100, 1 \leq n \leq 100, 1 \leq k \leq 10^{18}, 1 \leq a[i] \leq 10</math>.

			=== 分析 ===

			设 <math display="inline">f[i][j]</math> 表示考虑了前 <math display="inline">i</math> 个物品，总价值为 <math display="inline">j</math> 的方案数.

			则有状态转移方程 <math display="inline">\begin{aligned} f[i][j] = \sum_{l = 0}^{\lfloor \frac{j}{a[i]} \rfloor}{f[i - 1][j - l \times a[i]]} \end{aligned}</math>.

			接下来这一步被题解惊艳到了，拉格朗日插值！！！

			但体会一下也就明白了，还是很妙的感觉.

			=== 代码实现 ===

			<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
			using namespace std;

			typedef long long ll;
			typedef unsigned long long ull;

			const int M = (int)1e2;
			const int N = (int)5e5;
			const double eps = 1e-6;
			const int inf = 0x3f3f3f3f;
			const ll mod = (ll)1e9 + 7;

			int n; ll k;
			int a[M + 5];
			int f[N + 5];
			int y[M + 5];
			int pre[M + 5];
			int suf[M + 5];
			int fac[M + 5];
			int inv[M + 5];
			int invfac[M + 5];

			void init()
			{
			fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;
			for(int i = 2; i <= M; ++i)
			{
			fac[i] = 1ll * fac[i - 1] * i % mod;
			inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;
			invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod;
			}
			}

			int gcd(int a, int b)
			{
			return b ? gcd(b, a % b) : a;
			}

			int Lagrange(int n, ll k)
			{
			if(k <= n + 1) return y[k];
			pre[0] = 1; for(int i = 1; i <= n + 1; ++i) pre[i] = (k - i) % mod * pre[i - 1] % mod;
			suf[n + 2] = 1; for(int i = n + 1; i >= 1; --i) suf[i] = (k - i) % mod * suf[i + 1] % mod;
			int ans = 0, cur;
			for(int i = 1; i <= n + 1; ++i)
			{
			cur = 1ll * pre[i - 1] * suf[i + 1] % mod * invfac[i - 1] % mod * invfac[n + 1 - i] % mod;
			if(n + 1 - i & 1) cur *= -1;
			cur = 1ll * cur * y[i] % mod;
			ans = (ans + cur) % mod;
			}
			ans = (ans % mod + mod) % mod;
			return ans;
			}

			void work()
			{
			scanf("%d %lld", &n, &k);
			int lcm = 1;
			for(int i = 1; i <= n; ++i) scanf("%d", &a[i]), lcm = lcm / gcd(lcm, a[i]) * a[i];
			memset(f, 0, sizeof(f)); f[0] = 1;
			int r = lcm * n;
			for(int i = 1; i <= n; ++i)
			{
			for(int j = a[i]; j <= r; ++j) f[j] = (f[j] + f[j - a[i]]) % mod;
			}
			for(int i = k % lcm; i < r; i += lcm) y[i / lcm + 1] = f[i];
			printf("%d\n", Lagrange(n - 1, k / lcm + 1));
			}

			int main()
			{
			// freopen("input.txt", "r", stdin);
			// freopen("output.txt", "w", stdout);
			// ios::sync_with_stdio(0);
			// cin.tie(0); cout.tie(0);
			init();
			int T; scanf("%d", &T);
			for(int ca = 1; ca <= T; ++ca)
			{
			// printf("Case #%d:\n", ca);
			work();
			}
			// work();
			// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
			return 0;
			}</syntaxhighlight>

	== [https://acm.hdu.edu.cn/showproblem.php?pid=6954 Problem E. Minimum spanning tree] ==		== [https://acm.hdu.edu.cn/showproblem.php?pid=6954 Problem E. Minimum spanning tree] ==

BreakFast: /* Problem C. Puzzle loop */ add C bitset

2021-07-29T15:41:21Z

Problem C. Puzzle loop: add C bitset

← Older revision		Revision as of 15:41, 29 July 2021
Line 240:		Line 240:
	}</syntaxhighlight>		}</syntaxhighlight>

			=== bitset 优化 ===

			<syntaxhighlight lang="cpp">#include <bits/stdc++.h>
			using namespace std;

			typedef long long ll;
			typedef unsigned long long ull;

			const int M = (int)1e6;
			const int N = (int)17;
			const double eps = 1e-6;
			const int inf = 0x3f3f3f3f;
			const ll mod = (ll)998244353;

			int n, m;
			char s[N + 5][N + 5];
			int dx[] = {0, 0, 1, -1};
			int dy[] = {1, -1, 0, 0};
			int row, col;
			bitset<614> a[2 * (N + 1) * (N + 1) + 5];

			inline int id(int x1, int y1, int x2, int y2)
			{
			if(x1 > x2) swap(x1, x2);
			if(y1 > y2) swap(y1, y2);
			if(x1 == x2) return (x1 - 1) * m + y1;
			else return (n + 1) * m + (x1 - 1) * (m + 1) + y1;
			}

			void build()
			{
			row = 0, col = (n + 1) * m + n * (m + 1);
			for(int i = 1; i <= n + 1; ++i)
			{
			for(int j = 1; j <= m + 1; ++j)
			{
			++row;
			a[row].reset();
			for(int k = 0, x, y; k < 4; ++k)
			{
			x = i + dx[k], y = j + dy[k];
			if(x < 1 \|\| x > n + 1 \|\| y < 1 \|\| y > m + 1) continue;
			a[row].set(id(x, y, i, j));
			}
			}
			}
			for(int i = 1; i <= n; ++i)
			{
			for(int j = 1; j <= m; ++j)
			{
			if(s[i][j] == '.') continue;
			++row;
			a[row].reset();
			a[row].set(id(i, j, i, j + 1));
			a[row].set(id(i, j, i + 1, j));
			a[row].set(id(i, j + 1, i + 1, j + 1));
			a[row].set(id(i + 1, j, i + 1, j + 1));
			a[row].set(col + 1, s[i][j] - '0');
			}
			}
			// for(int i = 1; i <= row; ++i)
			// {
			// bool f = 0;
			// for(int j = 1; j <= col; ++j)
			// {
			// if(!a[i][j]) continue;
			// if(f) printf(" ^ ");
			// printf("x(%d)", j);
			// f = 1;
			// }
			// printf(" = 0\n");
			// }
			}

			int gauss(int n, int m)
			{
			int c, r;
			for(c = 1, r = 1; c <= m; ++c)
			{
			int t = r;
			for(int i = r; i <= n; ++i)
			{
			if(a[i][c]) t = i;
			}
			if(!a[t][c]) continue;
			swap(a[t], a[r]);
			for(int i = 1; i <= n; ++i)
			{
			if(i == r) continue;
			if(a[i][c]) a[i] ^= a[r];
			}
			++r;
			}
			for(int i = r; i <= n; ++i)
			{
			if(a[i][m + 1]) return -1;//无解
			}
			return m - r + 1;//自由元个数
			}

			ll quick(ll a, ll b, ll p = mod)
			{
			ll s = 1;
			while(b)
			{
			if(b & 1) s = s * a % p;
			a = a * a % p;
			b >>= 1;
			}
			return s;
			}

			void work()
			{
			scanf("%d %d", &n, &m);
			--n, --m;
			for(int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
			build();
			int r = gauss(row, col);
			if(r == -1) printf("0\n");
			else printf("%lld\n", quick(2, r));
			}

			int main()
			{
			// freopen("input.txt", "r", stdin);
			// freopen("output.txt", "w", stdout);
			// ios::sync_with_stdio(0);
			// cin.tie(0); cout.tie(0);
			int T; scanf("%d", &T);
			for(int ca = 1; ca <= T; ++ca)
			{
			// printf("Case #%d:\n", ca);
			work();
			}
			// work();
			// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
			return 0;
			}</syntaxhighlight>
	[https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop]		[https://acm.hdu.edu.cn/showproblem.php?pid=6953 Problem D. Another thief in a Shop]

BreakFast: update C

2021-07-29T15:28:09Z

update C

Show changes

BreakFast: update AEFGHIJK

2021-07-29T13:58:35Z

update AEFGHIJK

Show changes

BreakFast: add week 6 contest

2021-07-20T14:46:37Z

add week 6 contest

New page

__TOC__
== Replay ==

== Problem A ==