https://ac.nowcoder.com/acm/contest/1087
C - 斐波那契数列卷积
题意:给定 n,求 an=∑k=0nFn−k×Fk,q≤n≤1018,其中 F 是斐波那契数列,F0=0,F1=1。
先拆开来看看
anan−1an−2=F0Fn+F1Fn−1+⋯+FnF0=F0Fn−1+F1Fn−2+⋯+Fn−1F0=F0Fn−2+F1Fn−3+⋯+Fn−2F0
则自然想到把 an−1,an−2 加起来看看。
最终得到 an=an−1+an−2+Fn−1
再矩阵快速幂同时求得 F,a.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
| #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std; #define ll long long #define ull unsigned ll const int N = 100 + 10; const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 998244353; const ll inv2 = (mod + 1) / 2; struct Mat { ll a[N][N]; int r, c; Mat(int _r, int _c) { r = _r, c = _c, memset(a, 0, sizeof(a)); } }; Mat operator * (Mat X, Mat Y) { Mat Z(X.r, Y.c); for (int i = 0; i < X.r; ++i) { for (int j = 0; j < Y.c; ++j) { for (int k = 0; k < X.c; ++k) { Z.a[i][j] = (Z.a[i][j] + 1ll * X.a[i][k] * Y.a[k][j] % mod) % mod; } } } return Z; } Mat pow(Mat a, ll n) { Mat res(a.r, a.c); for (int i = 0; i < a.r; i++) res.a[i][i] = 1; while (n) { if (n & 1) res = res * a;; a = a * a; n >>= 1; } return res; } ll n; Mat A(4, 1); Mat B(4, 4); int main() { scanf("%lld", &n); A.a[2][0] = 1; B.a[0][0] = B.a[0][1] = B.a[0][2] = B.a[1][0] = B.a[2][2] = B.a[2][3] = B.a[3][2] = 1; A = pow(B, n - 1)*A; printf("%lld\n", A.a[0][0]); return 0; }
|
E - 树上逆序对
题意:给定一棵树,有点权,定义树上逆序对:x 是 y 的祖先,且 x 的点权大于 y。可以进行任意次修改,每次修改把一个点权变为相反数,多次询问,问能否使得逆序对数为 k。
树状数组+bitset优化可行性背包
最关键的点在于 一对点中绝对值大的那个可以决定这一对是否为逆序对,而绝对值小的那个点无论是否修改都没有影响。
所以只要对每个点找出它的祖先中比他小的点,以及它的子树中比他小的点。
这可以通过dfs的同时维护点权的树状数组得到,只要利用好欧拉序。
再做可行性背包,若不修改,则该点贡献为子树中比他小的点数,若修改,则为祖先中比他小的点数。
复杂度差一点,所以再用bitset优化。
注意bitset不能开太大,否则会T。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std; #define ll long long #define ull unsigned ll const int N = 2e5 + 10; const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 998244353; const ll inv2 = (mod + 1) / 2; int n; int a[N], b[N], c[N]; vector<int>G[N], vc; int sum1[N], sum2[N]; void add(int q, int x, int sum[]) { for (int i = q; i <= n; i += (i&-i)) sum[i] += x; } int qry(int r, int sum[]) { int res = 0; for (int i = r; i; i -= (i&-i)) res += sum[i]; return res; } void dfs(int u, int _fa) { b[u] += qry(a[u] - 1, sum1); add(a[u], 1, sum1); int tmp = qry(a[u] - 1, sum2); add(a[u], 1, sum2); for (int v : G[u]) { if (v == _fa)continue; dfs(v, u); } c[u] += qry(a[u] - 1, sum2) - tmp; add(a[u], -1, sum1); } bitset<30010>dp; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%d", &a[i]), vc.push_back(a[i]); vc.push_back(0); sort(vc.begin(), vc.end()); vc.erase(unique(vc.begin(), vc.end()), vc.end()); for (int i = 1; i <= n; i++)a[i] = lower_bound(vc.begin(), vc.end(), a[i]) - vc.begin(); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); dp.reset(); dp[0] = 1; for (int i = 1; i <= n; i++) { dp = (dp << b[i]) | (dp << c[i]); } int q; scanf("%d", &q); while (q--) { int k; scanf("%d", &k); puts(dp[k] ? "Orz" : "QAQ"); } return 0; }
|
D - 放物品
题意:给定 n 个物品,规定第 i 个不能放在位置 pi 上,定义一种摆放方式的值:设 j>i,且 posj<posi,则产生贡献 ∣i−j∣×∣posj−posi∣,问所有合法排列的值之和。
首先发现每对物品是独立产生贡献的,所以可以两层循环枚举一对物品,计算贡献。
设这对物品为 i,j。
则有四种情况:
- i 放在 pj,j 放在 pi
- i 不放在 pj,j 不放在 pi
- i 放在 pj,j 不放在 pi
- i 不放在 pj,j 放在 pi
对于每种情况求出 ∑∣posi−posj∣,再乘以 ∣j−i∣,再由于其它物品没有确定,所以还要乘以方案数,最后四种情况求和,就是这对物品的贡献。
对于第 1 种情况,posi=pj,posj=pi,所以 ∑∣posi−posj∣=∣pj−pi∣,方案数就是 n−1 个物品全错排的方案数,记为 f[n].
对于第 2 种情况,首先需要求出合法的总距离 tsum,再容斥去掉 i 放在 pj 或 j 放在 pi 时的距离和,方案数等于有 2 个物品没有对应位置的错排数,记为 g[n]。
对于第 3 种情况,同样求出总距离后去掉 j 放在 pi 的距离和,方案数等于有 1 个物品没有对应位置的错排数,记为 h[n]。
对于第 4 种情况,同样求出总距离后去掉 i 放在 pj 的距离和,方案数等于有 1 个物品没有对应位置的错排数,记为 h[n]。
下面求 f[n],g[n],h[n]。
f[n] 就是全错排,不多说了,f[n]=(f[n−1]+f[n−2])×(n−1).
h[n] 是有 1 个物品没有对应位置的错排,讨论那个物品放在那个没有对应物品的位置上,还是放在有对应物品的位置上,所以有 h[n]=f[n−1]+(n−1)×h[n−1].
g[n] 是有 2 个物品没有对应位置的错排,讨论这 2 个物品,分别放在没有对应物品的位置上还是放在有对应物品的位置上,所以有 g[n]=2f[n−2]+(n−2)×(n−3)×g[n−2]+4(n−2)×h[n−2].
还要注意的是要先从总距离中去除 i 放 pi 或 j 放 pj 这种不合法的情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| #include <bits/stdc++.h> #define debug(x) cout << #x << ":\t" << (x) << endl; using namespace std; #define ll long long #define ull unsigned ll const int N = 2e5 + 10; const int INF = 0x3f3f3f3f; const ll inf = 0x3f3f3f3f3f3f3f3f; const ll mod = 998244353; const ll inv2 = (mod + 1) / 2; int T; int n; int p[N]; ll f[N], g[N], h[N]; int main() { f[0] = 1; f[1] = 0; f[2] = 1; for (int i = 3; i < N; i++)f[i] = (f[i - 1] + f[i - 2])*(i - 1) % mod; h[0] = h[1] = 1; for (int i = 2; i < N; i++)h[i] = (f[i - 1] + (i - 1)*h[i - 1] % mod) % mod; g[0] = g[1] = 1; g[2] = 2; for (int i = 3; i < N; i++)g[i] = (2 * f[i - 2] % mod + (i - 2)*(i - 3) % mod*g[i - 2] % mod + 4 * (i - 2) % mod*h[i - 2] % mod) % mod; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; i++)scanf("%d", &p[i]); ll sum = 0; for (int i = 1; i <= n; i++)sum = (sum + i * (n - i) % mod) % mod; ll ans = 0; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { ll tsum = sum; if (p[i] > p[j])tsum = (tsum - (p[i] - 1)*p[i] / 2 % mod - (1 + n - p[j])*(n - p[j]) / 2 % mod + (p[i] - p[j]) + 2 * mod) % mod; else tsum = (tsum - (p[i] - 1)*p[i] / 2 % mod - (1 + n - p[j])*(n - p[j]) / 2 % mod + 2 * mod) % mod; if (p[j] > p[i])ans = (ans + (j - i)*(p[j] - p[i]) % mod*f[n - 2] % mod) % mod; ll s1 = (p[j] - 1)*p[j] / 2 % mod, s2 = (1 + n - p[i])*(n - p[i]) / 2 % mod; ll s; if (p[j] > p[i])s = (tsum - s1 - s2 + p[j] - p[i] + 2 * mod) % mod; else s = (tsum - s1 - s2 + 2 * mod) % mod; ans = (ans + s * (j - i) % mod*g[n - 2] % mod) % mod; s = (s1 - max(0, p[j] - p[i]) + mod) % mod; ans = (ans + s * (j - i) % mod*h[n - 2] % mod) % mod; s = (s2 - max(0, p[j] - p[i]) + mod) % mod; ans = (ans + s * (j - i) % mod*h[n - 2] % mod) % mod; } } printf("%lld\n", ans); } return 0; }
|