C
设 为字符集大小。
因为是排列计数,所以考虑使用 而不是
。对于一种字符,我们列出它方案数对应的
如下:
那全部卷起来就是答案的生成函数:
接下来暴力展开式子,枚举后面那个多项式选了多少个
由于只关心 的大小,于是设
为前
个字符,选取
个字符的多项式相乘的答案。转移只需要考虑第
个选不选即可。这部分时间复杂度
。
现在式子变成了:
因为 的次数最高为
,所以暴力展开
来卷。
但是如何快速求出 的第
项系数?第
项的系数就是长为
的序列,共有
种数可以放,最后能构成的序列的方案数。也就是
。然后要除以一个
表示为
形式。也就是:
乘 是为了抵消
中的
。这部分时间复杂度
。
#include <bits/stdc++.h> #define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++) #define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--) #define pb push_back using namespace std; typedef long long LL; const int N = 5e4+9; const int M = 1e7+9; const int p = 998244353; int w, c[20], len, tot, n, q, r[N << 1]; LL a[N * 2], f[20][N * 2], ans; LL fac[M], ifac[M]; int read() { int f = 0, x = 0; char ch = getchar(); while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return f ? -x : x; } int inv(int x, int base = p - 2) { int res = 1; while (base) { if (base & 1) res = 1ll * res * x % p; x = 1ll * x * x % p; base >>= 1; } return res; } void FFT(LL a[], int len, int op) { For(i, 0, len - 1) r[i] = r[i >> 1] >> 1 | ((i & 1) * (len >> 1)); For(i, 0, len - 1) if (i < r[i]) swap(a[i], a[r[i]]); for (int i = 1; i < len; i <<= 1) { LL wn = inv(3, (p - 1) / (i << 1)); if (op == -1) wn = inv(wn, p - 2); for (int j = 0; j < len; j += i << 1) { LL w = 1, x, y; For(k, 0, i - 1) { x = a[j + k], y = a[i + j + k] * w % p, w = w * wn % p; a[j + k] = (x + y) % p, a[i + j + k] = (x - y + p) % p; } } } if (op == -1) { LL x = inv(len, p - 2); For(i, 0, len - 1) a[i] = a[i] * x % p; } } void work() { for (len = 1; len <= tot; len <<= 1); f[0][0] = 1; FFT(f[0], len, 1); For(i, 0, w - 1) { For(j, 0, len - 1) a[j] = 0; For(j, 0, c[i]) a[j] = (p - 1) * ifac[j] % p; FFT(a, len, 1); Rof(j, w, 1) For(k, 0, len - 1) f[j][k] = (f[j][k] + f[j - 1][k] * a[k]) % p; } For(i, 0, w) FFT(f[i], len, -1); } int main() { w = read(); For(i, 0, w - 1) c[i] = read() - 1, tot += c[i]; int m = 10000000; fac[0] = 1; For(i, 1, m) fac[i] = fac[i - 1] * i % p; ifac[m] = inv(fac[m], p - 2); Rof(i, m, 1) ifac[i - 1] = ifac[i] * i % p; work(); q = read(); while (q--) { n = read(), ans = 0; For(i, 0, w) { LL x = inv(w - i, n); LL invx = inv(w - i, p - 2); For(j, 0, min(n, tot)) { if (j == n) x = 1; ans = (ans + x * f[i][j] % p * ifac[n - j]) % p, x = x * invx % p; } } printf("%lld\n", ans * fac[n] % p); } return 0; }
E
考虑二维上的问题。如果对于一个点 存在一个点
满足
,那么能满足
的一定能满足
,所以
是无用的。把所有的无用点剔除,剩下的点呈阶梯状。只需要用二维前缀和即可算出贡献。
若需要动态加入点,则需要维护所谓的”有用点“数组,并让其有序(按第一关键字升序排序)。显对于所有的 一定满足
且
(不然一定有点会被剔除)。当新加入一个点
时,可以通过二分,找到
应该所在的位置,看是否能剔除其他点或被剔除。
于是我们把所有的点先按第三维升序排序,然后每一层动态加入点进行修改。并在三维差分数组上修改。由于每个点被加入一次,删除一次,所以总时间复杂度是 。最后做一次三维前缀和即可
查询答案。时间复杂度
。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 10; const int M = 4e2 + 9; const int p = 998244353; int read() { int f = 0, x = 0; char ch = getchar(); while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return f ? -x : x; } set<pair<int, int>>s[N]; struct node { int y, z, id; }; vector<node>e[M]; int dp[M][M][M], a[M][M]; void add(int x1, int y1, int x2, int y2) { a[x1][y1]++; a[x1][y2]--; a[x2][y1]--; a[x2][y2]++; } void insert(int i, int y, int z) { auto it = s[i].lower_bound({y, z}); int last = y; auto now = it; int z1 = now == s[i].begin() ? M - 1 : (--now)->second; if (z1 <= z) return; while (1) { if (it == s[i].end()) break; add(last, z, it->first, z1); if (it->second < z) break; now = it++; last = now->first; z1 = now->second; s[i].erase(now); } s[i].insert({y, z}); } int n, m, q; int main() { n = read(), q = read(); for (int i = 1; i <= n; i++) { s[i].insert({401, 0}); m = read(); for (int j = 1; j <= m; j++) { int x = read(), y = read(), z = read(); e[x].push_back({y, z, i}); } } for (int i = 1; i <= 400; i++) { for (auto it : e[i]) insert(it.id, it.y, it.z); for (int y = 1; y <= 400; y++) for (int z = 1; z <= 400; z++) dp[i][y][z] = dp[i][y - 1][z] + dp[i][y][z - 1] - dp[i][y - 1][z - 1] + a[y][z]; } int seed; seed = read(); mt19937 rng(seed); uniform_int_distribution<> u(1, 400); int lastans = 0; ll ans = 0; for (int i = 1; i <= q; i++) { int IQ = (u(rng)^lastans) % 400 + 1; // The IQ of the i-th friend int EQ = (u(rng)^lastans) % 400 + 1; // The EQ of the i-th friend int AQ = (u(rng)^lastans) % 400 + 1; // The AQ of the i-th friend lastans = dp[IQ][EQ][AQ]; ans = (lastans + ans * seed % p) % p; } printf("%lld\n", ans); return 0; }
G
发现答案之多与三条射线有关,所以暴力是 的。
接下来,对于射线条数以及形态进行分类讨论。(下文的其余情况均可通过旋转整个图形得到):
条,当且仅当不存在射线
条,选取底部和顶部中最左/右的射线,并且左右两边不能有射线
条
- 平行,则只需要把底部和顶部的射线合并起来,选取相邻两条更新答案。
- 垂直,则只可能在整个图形左上/左下(剩下的旋转图形即可计算),枚举哪一方射线先出来即可。
条
+---------------+ |--------->| | | ^ | | | | | | | | v | +---------------+
一种是按照底边,侧边,顶边的顺序。枚举底边射线
,然后在
到
右侧下一根射线这个区间内,在顶部找到最靠右的射线。然后侧边的射线要尽可能高。
+---------------+ |-------------> | | ^ ^ | | | | | | | | | +---------------+
另一种是侧边+两个底边。这个显然只需要选择底边相邻两个,然后侧边尽可能高。
具体细节注意一下就好了。
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1e5 + 9; const int lim = 2e9; struct node { int x, y; } a[N]; int n, m, k, U[N], b[N], D[N]; int ans; int read() { int f = 0, x = 0; char ch = getchar(); while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return f ? -x : x; } void work() { int l1 = 0, l2 = 0, l3 = 0; int lmn = lim, L = -lim, rmn = lim, R = -lim, mx = -lim; for (int i = 1; i <= k; ++i) { if (a[i].y == 0) D[++l1] = a[i].x, b[++l2] = a[i].x; else if (a[i].x == 0) lmn = min(lmn, a[i].y), L = max(L, a[i].y); else if (a[i].y == m) U[++l3] = a[i].x, b[++l2] = a[i].x; else if (a[i].x == n) rmn = min(rmn, a[i].y), R = max(R, a[i].y); } if (!l1) return; sort(D + 1, D + 1 + l1); D[0] = 0; D[l1 + 1] = n; sort(b + 1, b + 1 + l2); mx = max(L, R); sort(U + 1, U + 1 + l3); U[0] = 0; U[l3 + 1] = n; ans = max(ans, L < 0 ? b[1] * m : lmn * D[1]); ans = max(ans, R < 0 ? (n - b[l2]) * m : (n - D[l1]) * rmn); for (int i = 2; i <= l2; ++i) ans = max(ans, m * (b[i] - b[i - 1])); if (mx >= 0) for (int i = 2; i <= l1; ++i) ans = max(ans, (D[i] - D[i - 1]) * mx); if (L >= 0) { for (int i = 1; i <= l1; ++i) { int r = U[lower_bound(U + 1, U + 1 + l3, D[i + 1]) - U - 1]; if (r > D[i]) ans = max(ans, (r - D[i]) * L); int l = U[lower_bound(U + 1, U + 1 + l3, D[i]) - U - 1]; if (!l) ans = max(ans, (D[i] - l) * (m - L)); } } if (R >= 0) { for (int i = 1; i <= l1; ++i) { int l = U[upper_bound(U + 1, U + 1 + l3, D[i - 1]) - U]; if (l < D[i]) ans = max(ans, (D[i] - l) * R); int r = U[upper_bound(U + 1, U + 1 + l3, D[i]) - U]; if (r == n) ans = max(ans, (r - D[i]) * (m - R)); } } } void rebuild() { for (int i = 1; i <= k; ++i) { if (a[i].y == 0) a[i].y = n - a[i].x, a[i].x = 0; else if (a[i].x == 0) a[i].x = a[i].y, a[i].y = n; else if (a[i].y == m) a[i].y = n - a[i].x, a[i].x = m; else if (a[i].x == n) a[i].x = a[i].y, a[i].y = 0; } swap(n, m); } signed main() { int T = read(); while (T--) { k = read(); n = read(); m = read(); ans = 0; for (int i = 1; i <= k; ++i) a[i] = {read(), read()}; work();rebuild(); work();rebuild(); work();rebuild(); work(); printf("%lld\n", ans); } return 0; }
I
设整张地图为 ,飞船为
(都是
维数组)。
由于 很小,若一种放置方式对于任意
都满足
中值为
的位置对应在
中的值大于等于
,那么这个放置方式也是合法的。
具体的,将 中值为
的点设为
,其余地方设为
。把
中值大于等于
的点设为
,其余地方设为
。若一种放置方式,存在
对应位置都为
,那么就不合法。
到此,可以用 的与操作优化,但显然是过不了的。
维的操作很麻烦,不妨化成一维上的数组:
。
同理, 也化成类似形式。为了与
匹配,多余的地方置为
。即:
现在就变成了 维的问题!
对于一种匹配,想快速得到 中是否不存在位置同为
,即按位相乘的和是否不
。这启发我们想到
。只需要乘一次,即可得到所有的匹配结果。但是注意
不能放出
的位置(指在
维下),这个判断一下即可。设
,时间复杂度
。
#include <bits/stdc++.h> using namespace std; const int N = 6; const int p = 998244353; const int G = 3; int k; int n[N], sz; vector<int> T, S; int m[N]; int len1, len2; int a[N]; vector <int> A, B, val; int read() { int f = 0, x = 0; char ch = getchar(); while (!isdigit(ch)) { f |= (ch == '-'); ch = getchar(); } while (isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); } return f ? -x : x; } int get(int *a) { int res = 0; for (int i = 1; i <= k; i++) res = res * n[i] + a[i]; return res; } int check(int x) { for (int i = k; i; i--) { if (x % n[i] >= m[i]) return 0; x /= n[i]; } return k; } int check2(int x) { for (int i = k; i; i--) { if (x % n[i] > n[i] - m[i]) return 0; x /= n[i]; } return 1; } int len; int inv(int x, int base = p - 2) { int res = 1; while (base) { if (base & 1) res = 1ll * res * x % p; x = 1ll * x * x % p; base >>= 1; } return res; } void FFT(vector<int> &A, int op = 0) { for (int i = 0; i < len; i++) { int r = 0; for (int j = i, k = len; k > 1; j >>= 1, k >>= 1) r = (r << 1) | (j & 1); if (i < r) swap(A[i], A[r]); } for (int i = 1; i < len; i <<= 1) { int wn = inv(G, (p - 1) / (i << 1)); for (int j = 0; j < len; j += (i << 1)) { int w = 1; for (int k = 0; k < i; k++) { int x = A[j + k], y = 1ll * w * A[j + k + i] % p; A[j + k] = (x + y) % p; A[j + k + i] = (x + p - y) % p; w = 1ll * w * wn % p; } } } if (op == -1) { for (int i = 1; i < (len >> 1); i++) swap(A[i], A[len - i]); int INV = inv(len); for (int i = 0; i < len; i++) A[i] = 1ll * A[i] * INV % p; } } void mul(vector<int> &A, vector<int> &B) { len = 1; while (len < A.size() + B.size()) len <<= 1; A.resize(len); B.resize(len); FFT(A); FFT(B); for (int i = 0; i < len; i++) A[i] = 1ll * A[i] * B[i] % p; FFT(A, -1); } int ans; int main() { k = read(); sz = 1; for (int i = 1; i <= k; i++) { n[i] = read(); sz *= n[i]; } T.resize(sz); S.resize(sz); for (int i = 0; i < sz; i++) T[i] = k; len1 = read(); for (int i = 1; i <= len1; i++) { int v; for (int j = 1; j <= k; j++) a[j] = read(); v = read(); T[get(a)] = v; } for (int i = 1; i <= k; i++) m[i] = read(); val.resize(sz); for (int i = 0; i < sz; i++) { S[i] = check(i); val[i] = check2(i); } len2 = read(); for (int i = 1; i <= len2; i++) { int v; for (int j = 1; j <= k; j++) a[j] = read(); v = read(); S[get(a)] = v; } for (int i = 1; i <= k; i++) { A.resize(sz); B.resize(sz); for (int j = 0; j < sz; j++) { A[j] = T[j] < i; B[sz - j - 1] = S[j] == i; } mul(A, B); for (int j = 0; j < sz; j++) val[j] &= (A[j + sz - 1] == 0); } for (int i = 0; i < sz; i++) ans += val[i]; printf("%d\n", ans); return 0; }
M
对于两个点 ,若钦定
在直线上的投影在
的左边,那么会有一个
° 的区间范围限制。对于所有的相邻两点都计算出这个限制,取交就是直线方向。而直线具体位置是没有关系的。
#include <bits/stdc++.h> #define int long long using namespace std; const int N = 1e5 + 9; int n; struct node { int x, y; int operator*(node &X)const { return x * X.y - y * X.x; } }; node a[N], l, r, L, R; signed main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y; L.x = L.y = 1; for (int i = 2; i <= n; i++) { node b; b.x = a[i].x - a[i - 1].x; b.y = a[i].y - a[i - 1].y; if (b.x == 0 && b.y == 0) continue; r.y = -b.x; l.x = -b.y; l.y = b.x; r.x = b.y; if (i == 2) { L = l, R = r; continue; } if ((l * R) > 0 && (r * L) < 0) { puts("NO"); return 0; } if ((l * L) > 0) L = l; if ((r * R) < 0) R = r; } puts("YES"); cout << "0 0 "; cout << L.x << " " << L.y; }
全部评论
(0) 回帖