就是个等比数列，特判公比为 $1$ 的情况即可。
#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 9; const int N = 1e5 + 7; int qp(int a, int b = MOD - 2) { int ans = 1; while (b) { if (b & 1) ans = 1LL * ans * a % MOD; a = 1LL * a * a % MOD; b >>= 1; } return ans; } int M(int a) { if (a < 0) a += MOD; if (a >= MOD) a -= MOD; return a; } char s[N]; int main() { int n, a, b, k; scanf("%d%d%d%d", &n, &a, &b, &k); int q = 1LL * qp(qp(a, k)) * qp(b, k) % MOD; scanf("%s", s); int a1 = 0; for (int i = 0; i < k; i++) { int x = ((s[i] == ‘+‘) ? 1 : -1); a1 = M(a1 + 1LL * x * qp(a, n - i) % MOD * qp(b, i) % MOD); } if (q == 1) { int ans = 1LL * a1 * (n + 1) / k % MOD; printf("%d\n", ans); return 0; } int inv = qp(q - 1); int ans = 1LL * a1 * (qp(q, (n + 1) / k) - 1) % MOD * inv % MOD; printf("%d\n", ans); return 0; }
优先删除靠近叶子节点的偶数度数的节点，因为假如删了这个节点的父节点，就剩下两个点一条边了。
那这样肯定是不能删完的。
就搞出dfs序，倒着删，如果有偶数度数的就往下删，不往父节点方向走即可。
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 7; vector<int> G[N]; int degree[N], fa[N], dfn[N], tol; bool vis[N]; int ans[N], cnt; void dfs(int u, int pre) { fa[u] = pre; dfn[++tol] = u; for (auto v: G[u]) if (v != pre) dfs(v, u); } void dfs2(int u) { vis[u] = 1; ans[++cnt] = u; for (auto v: G[u]) { degree[v]--; if (v == fa[u] || vis[v]) continue; if (degree[v] % 2 == 0) dfs2(v); } } int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { int x; scanf("%d", &x); if (!x) continue; degree[i]++; degree[x]++; G[i].push_back(x); G[x].push_back(i); } dfs(1, 0); for (int i = tol; i >= 1; i--) { if (degree[dfn[i]] % 2 == 0) dfs2(dfn[i]); } if (cnt == n) { puts("YES"); for (int i = 1; i <= n; i++) printf("%d\n", ans[i]); } else { puts("NO"); } return 0; }
画图发现，对于不一样长度的矩形，它所具有的宽度集合必须一样，并且对应的 $c$ 个数必须成比例。
排个序排除一下这两种情况。
具体排列方式就与比例的约数有关了，比如对于长为 $3$ 的矩形，它具有的宽度集合为 $2$，$3$，$4$，个数分别为 $2$，$4$，$6$
那么基底就为 $1$ $2$ $3$，把它们拼在一起，就有两个这样的大矩形，那么排列方式就是两种，横着拼一起或者竖着拼一起。
也就是 gcd 的约数个数，但这只是一组的排列方式，因为要满足和其它组能拼成最后的大矩形，那么就是所有数的 gcd 的约数个数了。
#include <bits/stdc++.h> #define ll long long #define pii pair<ll, ll> #define fi first #define se second using namespace std; const int N = 2e5 + 7; struct P { ll w, h, c; void read() { scanf("%lld%lld%lld", &w, &h, &c); } bool operator < (const P &rhs) const { return w < rhs.w || (w == rhs.w && h < rhs.h); } } p[N]; vector<pii> vec[N]; ll base[N]; template<class T> T gcd(T a, T b) { while (b) { a %= b; swap(a, b); } return a; } int main() { //freopen("in.txt", "r", stdin); int n; scanf("%d", &n); for (int i = 1; i <= n; i++) p[i].read(); sort(p + 1, p + 1 + n); int cnt = 0; for (int i = 1; i <= n; i++) { if (p[i].w != p[i - 1].w) cnt++; vec[cnt].push_back(pii(p[i].h, p[i].c)); } ll g = 0; for (auto p: vec[1]) g = gcd(g, p.se); for (int i = 0; i < vec[1].size(); i++) base[i] = vec[1][i].se / g; bool flag = 0; for (int i = 2; i <=cnt && !flag; i++) { if (vec[i].size() != vec[i - 1].size()) { flag = 1; break; } for (int j = 0; j < vec[i].size(); j++) { if (vec[i][j].fi != vec[i - 1][j].fi) { flag = 1; break; } } if (flag) break; if (vec[i][0].se % base[0]) { flag = 1; break; } ll temp = vec[i][0].se / base[0]; for (int j = 1; j < vec[i].size(); j++) { if (vec[i][j].se / base[j] != temp) { flag = 1; break; } } } if (flag) { puts("0"); return 0; } g = 0; for (int i = 1; i <= cnt; i++) { g = gcd(g, vec[i][0].se / base[0]); } ll ans = 0; for (ll i = 1; i * i <= g; i++) { if (g % i) continue; ans++; if (g / i != i) ans++; } printf("%lld\n", ans); return 0; }
AC自动机直接做。或者哈希。
对长度相同的串同时查询，长度不同的串不超过 $\sqrt n$ 种。这样查询的复杂度是 $O(n \sqrt n)$ 的。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 100; const int sz = 26; vector<int> vec[N]; struct Aho { int trie[N][sz], tol, fail[N], pos[N], last[N]; void init() { tol = 0; newnode(); } int newnode() { for (int i = 0; i < sz; i++) trie[tol][i] = 0; fail[tol] = pos[tol] = 0; return tol++; } void ins(char *s, int index) { int len = strlen(s); int u = 0; for (int i = 0; i < len; i++) { int id = s[i] - ‘a‘; if (!trie[u][id]) trie[u][id] = newnode(); u = trie[u][id]; } pos[u] = index; } void build() { queue<int> que; for (int i = 0; i < sz; i++) if (trie[0][i]) que.push(trie[0][i]); while (!que.empty()) { int u = que.front(); que.pop(); for (int i = 0; i < sz; i++) { int &v = trie[u][i]; if (v) { fail[v] = trie[fail[u]][i]; que.push(v); last[v] = pos[fail[v]] ? fail[v] : last[fail[v]]; } else { v = trie[fail[u]][i]; } } } } void search(char *s) { int u = 0; for (int i = 0; s[i]; i++) { int id = s[i] - ‘a‘; int temp = trie[u][id]; u = temp; while (temp) { if (pos[temp]) vec[pos[temp]].push_back(i); temp = last[temp]; } } } } ac; char s[N], t[N]; int k[N], len[N]; int main() { // freopen("in.txt", "r", stdin); int n; scanf("%s%d", s, &n); ac.init(); for (int i = 1; i <= n; i++) { scanf("%d", k + i); scanf("%s", t); ac.ins(t, i); len[i] = strlen(t); } ac.build(); ac.search(s); for (int i = 1; i <= n; i++) { if (vec[i].size() < k[i]) { puts("-1"); continue; } int ans = 1e9; for (int l = 0, r = k[i] - 1; r < vec[i].size(); l++, r++) { ans = min(ans, vec[i][r] + len[i] - 1 - vec[i][l] + 1); } printf("%d\n", ans); } return 0; }
#include <bits/stdc++.h> #define ull unsigned long long using namespace std; const int N = 1e5 + 7; const ull BASE = 201326611; ull bit[N], Hash[N]; unordered_map<ull, int> id[N]; int vec[N], cnt; vector<int> pos[N]; ull get(int l, int r) { return Hash[r] - Hash[l - 1] * bit[r - l + 1]; } char s[N], t[N]; int k[N], l[N]; int main() { scanf("%s", s + 1); int len = strlen(s + 1); for (int i = bit[0] = 1; i <= len; i++) bit[i] = bit[i - 1] * BASE, Hash[i] = Hash[i - 1] * BASE + s[i]; int q; scanf("%d", &q); for (int i = 1; i <= q; i++) { scanf("%d%s", k + i, t + 1); l[i] = strlen(t + 1); ull temp = 0; for (int j = 1; j <= l[i]; j++) temp = temp * BASE + t[j]; id[l[i]][temp] = i; vec[++cnt] = l[i]; } sort(vec + 1, vec + 1 + cnt); cnt = unique(vec + 1, vec + 1 + cnt) - vec - 1; for (int i = 1; i <= cnt; i++) { int n = vec[i]; for (int ll = 1, rr = n; rr <= len; ll++, rr++) { ull temp = get(ll, rr); if (id[n].count(temp)) pos[id[n][temp]].push_back(ll); } } for (int i = 1; i <= q; i++) { int ans = 1e9; for (int ll = 0, rr = k[i] - 1; rr < pos[i].size(); ll++, rr++) ans = min(ans, pos[i][rr] + l[i] - 1 - pos[i][ll] + 1); printf("%d\n", (ans == 1e9) ? -1 : ans); } return 0; }
有转移方程 $$ f(x, y) = p_1 * f(x - 1, y) + p_2 * f(x, y - 1) + p_3 * f(x + 1, y) + p_4 * f(x, y + 1) + 1$$
有 $R ^ 2$ 个未知数，直接高斯消元解复杂度为 $O(R ^ 6)$
因为跟自己有关的项达不到 $R^2$ 的级别。所以只要对相邻这些消元即可。
#include <bits/stdc++.h> #define pii pair<int, int> #define fi first #define se second using namespace std; const int N = 105; const int M = 7850; const int MOD = 1e9 + 7; int n, p[4], ans[M], a[M][M]; const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; vector<pii> all; int qp(int a, int b = MOD - 2) { int ans = 1; while (b) { if (b & 1) ans = 1LL * ans * a % MOD; a = 1LL * a * a % MOD; b >>= 1; } return ans; } int main() { int R; scanf("%d", &R); int sum = 0; for (int i = 0; i < 4; i++) scanf("%d", p + i), sum += p[i]; sum = qp(sum); for (int i = 0; i < 4; i++) p[i] = 1LL * p[i] * sum % MOD; for (int i = -R; i <= R; i++) for (int j = -R; j <= R; j++) if (i * i + j * j <= R * R) all.push_back(pii(i, j)); n = all.size(); for (int i = 0; i < n; i++) { int x = all[i].fi, y = all[i].se; a[i][i] = a[i][n] = 1; for (int j = 0; j < 4; j++) { int u = x + dx[j], v = y + dy[j]; if (u * u + v * v <= R * R) a[i][lower_bound(all.begin(), all.end(), pii(u, v)) - all.begin()] = MOD - p[j]; } } for (int i = 0; i < n; i++) { vector<int> t = {n}; int u = min(i + R * 2 + 5, n); for (int j = i; j < u; j++) { if (a[i][j]) { t.push_back(j); } } int inv = qp(a[i][i]); for (int j = i + 1; j < u; j++) { if (a[j][i]) { int mul = 1LL * a[j][i] * inv % MOD; for (auto k: t) { a[j][k] = (a[j][k] - 1LL * mul * a[i][k] % MOD + MOD) % MOD; } } } } for (int i = n - 1; ~i; i--) { int val = a[i][n]; for (int j = i + 1; j < n; j++) { val = (val - 1LL * ans[j] * a[i][j] % MOD + MOD) % MOD; } ans[i] = 1LL * val * qp(a[i][i]) % MOD; } printf("%d\n", ans[lower_bound(all.begin(), all.end(), pii(0, 0)) - all.begin()]); return 0; }
Tinkoff Internship Warmup Round 2018 and Codeforces Round #475 (Div. 1)
原文：https://www.cnblogs.com/Mrzdtz220/p/11664625.html
