20220305 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

dp + 矩阵乘法，贪心 + 贪心 + 贪心，期望 dp + 线段树

# A. 【长沙2020年1月集训day10】黎曼几何

简单推式子题。

设第一个环到第二个环需要的次数为 $f_i$ ，第一个环到第三个环需要的次数位 $g_i$ 。

对于 $f_i$ ，先把前 $i - 1$ 个硬币扔到 ③ 上面，再把第 $i$ 个硬币扔到 ② 上面，最后把前 $i - 1$ 个硬币从 ③ 扔到 ② 上面（① $\rightarrow$ ③ 和 ③ $\rightarrow$ ② 是相等的）。

所以 $f_i = 2 \times g_{i - 1} + 1$ .
对于 $g_i$ ，同样考虑上述过程，不难推出 $g_i = 2 \times g_{i - 1} + f_i + 2$ .

然后发现需要矩阵加速一下，所以给他放到一个向量里面：

$\begin{vmatrix}1 & f_i & g_i\end{vmatrix}$

稍微推一下矩阵，可以推出：

$\begin{vmatrix}1 & f_i & g_i\end{vmatrix} * \begin{vmatrix}1 & 1 & 2 \\ 0 & 0 & 1 \\ 0 & 2 & 2 \end{vmatrix} = \begin{vmatrix}1 & f_{i + 1} & g_{i + 1}\end{vmatrix}$

但是每次都跑一遍 $\log n$ 的矩阵快速幂也会 T，所以还要使用光速幂，也就是把矩阵快速幂的结果记录下来，每次询问的时候直接调用矩阵即可。

（由于考场上一直在卡常，导致代码有些丑陋，甚至还把 $n$ 存了下来，排了个序，但还是没卡过去/kk）

#include <bits/stdc++.h>
#define ll long long

using namespace std;

namespace IO{
    inline ll read(){
        ll x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int mod = 998244353;
const int N = 2e6;
const int B = 1e6;
int T;
ll n[N];

struct matrix{
    int num[5][5];

    matrix() {memset(num, 0, sizeof(num));}
    inline void init() {num[0][0] = num[1][1] = num[2][2] = 1;}
    inline void Clear() {num[0][0] = num[0][1] = num[0][2] = num[1][0] = num[1][1] = num[1][2] = num[2][0] = num[2][1] = num[2][2] = 0;}

    matrix operator * (const matrix &b) const{
        matrix r;
        for(int i = 0; i < 3; ++i)
            for(int j = 0; j < 3; ++j){
                r.num[i][j] = (r.num[i][j] + 1ll * num[i][0] * b.num[0][j]) % mod;
                r.num[i][j] = (r.num[i][j] + 1ll * num[i][1] * b.num[1][j]) % mod;
                r.num[i][j] = (r.num[i][j] + 1ll * num[i][2] * b.num[2][j]) % mod;
            }
        return r;
    }

    matrix operator ^ (ll b) const{
        matrix r, a;
        memcpy(a.num, num, sizeof(num));
        r.init();
        for(; b; a = a * a, b >>= 1)
            if(b & 1) r = r * a;
        return r;
    }
}A, f, I, pw[2][N];

int a, b;

inline void prework(){
    I.num[0][0] = I.num[1][1] = I.num[2][2] = 1;
    pw[0][0] = pw[1][0] = I;
    for(int i = 1; i <= B; ++i) pw[0][i] = pw[0][i - 1] * A;
    for(int i = 1; i <= B; ++i) pw[1][i] = pw[1][i - 1] * pw[0][B];
}

inline matrix ksm(ll n) {return pw[1][n / B] * pw[0][n % B];}


signed main(){
    // freopen("riemannian.in", "r", stdin);
    // freopen("riemannian.out", "w", stdout);
    A.num[0][0] = A.num[0][1] = A.num[1][2] = 1, A.num[0][2] = A.num[2][1] = A.num[2][2] = 2;
    f.num[0][0] = f.num[0][1] = 1, f.num[0][2] = 2;
    prework();
    T = read();
    for(int i = 1; i <= T; ++i) n[i] = read();
    sort(n + 1, n + 1 + T);
    int pos;
    for(int i = 1; i <= T; ++i)
        if(n[i]){
            if(n[i] > 1)  A = ksm(n[i] - 1), f = f * A;
            a ^= f.num[0][1], b ^= f.num[0][2], pos = i;
            break;
        }
    for(int i = pos + 1; i <= T; ++i){
        if(n[i] - n[i - 1] == 0){a ^= f.num[0][1], b ^= f.num[0][2]; continue;}
        A = ksm(n[i] - n[i - 1]), f = f * A;
        a ^= f.num[0][1], b ^= f.num[0][2];
    }
    printf("%d %d\n", a, b);
    return 0;
}
// X.K.

# B. 【长沙2020年1月集训day10】代数几何

巨大贪心，你需要找到三个结论方可通过此题。

不难发现，在放数时有的时候会出现一些循环节，那么……

最重要的结论： 循环节个数为 $\gcd(n, k)$ 。

至于为什么，建议打表……

所以对于每个循环节我们分别考虑即可。

另外两个结论：

每一个循环节中的数一定是连续的。
摆放方式一定是： $\cdots, x - 3, x - 1, x, x - 2, x - 4, \cdots$

这两个都不难理解，大的数和大的数相乘一定更优，因此感性理解一下上面这两个结论都是正确的。

然后代码就十分的 $\text{easy}$ 了。

#include <bits/stdc++.h>
#define int long long

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 5010;
int n, m, ans;
int a[N], b[N], c[N];

inline int add(int x) {return x >= n ? x - n : x;}
inline int sub(int x) {return x < 0 ? x + n : x;}
inline bool cmp(int a, int b) {return a > b;}
inline int gcd(int a, int b) {return !b ? a : gcd(b, a % b);}

inline int calc(int n){
    if(n == 1) return a[0] * a[0];
    if(n == 2) return a[0] * a[1] * 2;
    int res = a[0] * a[1] + a[0] * a[2] + a[n - 2] * a[n - 1];
    for(int i = 3; i < n; ++i) res += a[i] * a[i - 2];
    return res;
}

inline void solve(int k){
    int t = gcd(n, k);
    int len = n / t, cnt = 0;
    ans = 0;
    for(int l = 1; l <= t; ++l){
        for(int i = 0; i < len; ++i) a[i] = b[cnt++];
        ans += calc(len);
    }
    write(ans), puts("");
}

signed main(){
    n = read();
    for(int i = 0; i < n; ++i) a[i] = b[i] = read();
    sort(b, b + n, cmp);
    m = read();
    while(m--) solve(read());
    return 0;
}
// X.K.

# C. 【长沙2020年1月集训day10】几何考试

考场上甚至连题目都没有看懂，遗憾离场了 QwQ

我现在只会 80pts 做法，满分做法先咕了。

题目就是要求别人对你排名贡献的期望和（我一直以为是一个人总排名的期望）。

我的做法是先对每个人排序，按照左端点从小到大排序，相同的按右端点从小到大排。

设 $p_{i, j}$ 表示 $i$ 赢 $j$ 的概率（由于贡献都是 1，所以概率等于期望）。

对于两个人 $i, j(i \leq j)$ ，此时 $j$ 的得分区间一定在 $i$ 的右边，分类讨论一下：

$i, j$ 得分区间交叉：如果 $i$ 想赢 $j$ ，那么只有 $i, j$ 得分都在交叉的那段区间才行，设交叉区间长度为 $b$ ，那么 $p_{i, j} = \frac b{len_i} \times \frac b{len_j} \times \frac12$ .
$i, j$ 得分区间不相交：此时 $i$ 必输，所以 $p_{i, j} = 0$
$i$ 的得分区间包含 $j$ ：此时 $i$ 获胜概率为 $i$ 在交叉区间得分的概率除以二加上 $i$ 在 $j$ 得分区间右边的概率，假设交叉区间长度为 $b$ ， $c = r_i - r_j$ ，那么 $p_{i, j} = \frac b{len_i} \times \frac12 + \frac {c}{len_i}$ 。

$p_{j, i} = 1 - p_{i, j}$ .

然后对于每个人求个和即可。

#include <bits/stdc++.h>

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 5010;
int n;
struct node{
    int l, r, id;
    bool operator < (const node &b) const{
        return l != b.l ? l < b.l : r < b.r;
    }
}a[N];
double p[N][N], ans[N];

signed main(){
    n = read();
    for(int i = 1; i <= n; ++i) a[i].l = read(), a[i].r = read(), a[i].id = i;
    sort(a + 1, a + 1 + n);
    for(int i = 1; i <= n; ++i)
        for(int j = i + 1; j <= n; ++j){// p[i][j]: p[i win j]
            if(i == j) continue;
            int l1 = a[i].l, l2 = a[j].l, r1 = a[i].r, r2 = a[j].r;
            double a = l2 - l1, b = r1 - l2, c = abs(r2 - r1), len1 = r1 - l1, len2 = r2 - l2;
            if(l1 <= l2 && r1 <= r2) p[i][j] = (((b / len1) * (b / len2) / 2));
            if(r1 < l2) p[i][j] = 0;
            if(l1 <= l2 && r1 >= r2) p[i][j] = ((c / len1) + ((len2 / len1) / 2));
            p[j][i] = 1 - p[i][j];
        }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j) ans[a[i].id] += p[j][i];
    for(int i = 1; i <= n; ++i) printf("%.8lf\n", ans[i] + 1);
    return 0;
}
// X.K.

# A. 【长沙2020年1月集训day10】黎曼几何

# B. 【长沙2020年1月集训day10】代数几何

# C. 【长沙2020年1月集训day10】几何考试

20220304

P6047 丝之割 题解

P6047 丝之割题解