A Inverse
题目大意 ： 给一个排列，翻转k次，问最终逆序对个数的期望值
-
定义f[k][i][j]为翻转了k次后a[i]<a[j]的概率，每次可以枚举翻转区间进行转移，复杂度 (O(n^4k))
-
对于一个区间l,r
-
如果 (lleq ileq r<j)，改变 i 的位置，从 f[k-1][l+r-i][j] 转移来
-
如果 (i<lleq jleq r), 改变 j 的位置，从 f[k-1][i][l+r-j] 转移来
-
如果 (lleq i<jleq r), i,j 位置都改变，从 f[k-1][l+r-i][l+r-j] 转移来
-
-
然后在用两个前缀和分别优化这3种转移就好了
Code
Show Code
#include <cstdio>
#define Mod(x) ({ int xx = x; xx > M ? xx - M : xx; })
using namespace std;
const int N = 505, M = 1e9 + 7;
int n, k, a[N], f[N][N], s1[N][N], s2[N][N], s3[N][N], s4[N][N], s5[N][N], s6[N][N], ans, p = 1;
int Pow(int a, int k, int ans = 1) {
for (; k; k >>= 1, a = 1ll * a * a % M)
if (k & 1) ans = 1ll * ans * a % M;
return ans;
}
int Cal(int x) {
return x * (x + 1) / 2;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
f[i][j] = a[i] > a[j];
while (k--) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
s1[i][j] = Mod(s1[i][j-1] + f[i][j]);
s2[i][j] = Mod(s2[i][j-1] + s1[i][j]);
s3[i][j] = Mod(s3[i-1][j] + f[i][j]);
s4[i][j] = Mod(s4[i-1][j] + s3[i][j]);
s5[i][j] = Mod(s5[i-1][j-1] + f[i][j]);
s6[i][j] = Mod(s6[i-1][j-1] + s5[i][j]);
}
}
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
f[i][j] = (f[i][j] * (1ll * Cal(i-1) + Cal(j-i-1) + Cal(n-j)) + s2[i][n] + s2[i][i-1] - s2[i][n+i-j] + M - s2[i][j-1] + M + s4[j-1][j] - s4[j-i-1][j] + M - s4[i-1][j] + M + s6[n][n+i-j] - s6[n-i][n-j] + M - s6[j-1][i-1] + M) % M;
p = 1ll * p * Cal(n) % M;
for (int i = 1; i <= n; ++i)
for (int j = 1; j < i; ++j)
f[i][j] = Mod(p - f[j][i] + M);
}
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
if ((ans += f[i][j]) >= M) ans -= M;
printf("%lld
", 1ll * ans * Pow(p, M - 2) % M);
return 0;
}
B Subsequence
题目大意 ： 定义一个长度为k的序列B的权值是 (sum_{i-1}^{k}i imes B_i)，给一个长度为n的序列问长度分别为1到n的子序列最大权值
-
n2的dp很好写，f[i][j]表示前i个数选j个的最大权值，转移的话就是f[i][j]=max(f[i-1][j],f[i-1][j-1]+a[i]*j)
-
然后发现一个性质就是如果对于一个j来说，f[i-1][j-1]+a[i]*j > f[i-1][j]，那么更大的j也会满足，就是说有一个更新了，后面的都要更新
-
然后设g[i][j]=g[i][j]-g[i][j-1]，假设第1个更新的位置是j，那么g[i]和g[i-1]的区别就是g[i][j]变成a[i]*j,后面的g[i][k]变成g[i-1][k-1]+a[i]
-
也就是进行了插入一个a[i]*j，然后对后面的数区间加a[i]，可以用splay来维护
Code
Show Code
#include <cstdio>
#define Get(x) (t[fa[x]][1] == x)
using namespace std;
const int N = 1e5 + 5;
int read(int x = 0, int f = 1, char c = getchar()) {
for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
return x * f;
}
int n, t[N][2], fa[N], sz[N], rt, stk[N], tp;
long long tag[N], w[N], ans;
void Pushup(int x) {
sz[x] = sz[t[x][0]] + sz[t[x][1]] + 1;
}
void Rotate(int x) {
int y = fa[x], z = fa[y], k = Get(x), B = t[x][k^1];
t[z][Get(y)] = x; fa[x] = z;
t[x][k^1] = y; fa[y] = x;
t[y][k] = B; fa[B] = y;
Pushup(y); Pushup(x);
}
void Uptate(int x, long long val) {
w[x] += val; tag[x] += val;
}
void Pushdown(int x) {
if (!tag[x]) return;
Uptate(t[x][0], tag[x]);
Uptate(t[x][1], tag[x]);
tag[x] = 0;
}
void Splay(int x, int to = 0) {
for (int y = x; y != to; y = fa[y]) stk[++tp] = y;
while (tp) Pushdown(stk[tp--]);
while (fa[x] != to) {
int y = fa[x];
if (fa[y] != to) Get(x) != Get(y) ? Rotate(x) : Rotate(y);
Rotate(x);
}
if (!to) rt = x;
}
void Dfs(int x) {
if (!x) return;
Pushdown(x);
Dfs(t[x][0]);
printf("%lld ", ans += w[x]);
Dfs(t[x][1]);
}
int main() {
n = read(); w[1] = read(); sz[1] = rt = 1;
for (int i = 2; i <= n; ++i) {
int val = read(), x = rt, sum = 1, lt, k;
while (x) {
Pushdown(lt = x);
if (w[x] > 1ll * val * (sum + sz[t[x][0]]))
sum += sz[t[x][0]] + 1, k = 1;
else k = 0;
x = t[x][k];
}
t[lt][k] = i; fa[i] = lt; w[i] = 1ll * val * sum;
Splay(i); Uptate(t[i][1], val);
}
Dfs(rt);
return 0;
}
C Convex (Unaccepted)
题目大意 ：
Code
Show Code