跳转至

251121 模拟赛

T1

给定 \(n\) 个正整数，用加号乘号和小括号组成一个表达式，最大化表达式的值。

\(n\le 10^5,~a_i\le 10^6\)

根据经典结论，把一堆 \(1\) 分组相乘，肯定是 \(3\) 个一组最优。因此我们尽可能的凑出 \(3\)，凑不完的凑 \(2\) 或者 \(4\)，更大的数直接乘起来。

T2

简单分讨即可

T3

有 \(n\) 把椅子排成一圈，初始时第 \(i\) 个人坐在第 \(i\) 把椅子上。有两种操作：

  • + p：每个人顺时针移动 \(p\) 步，坐到新椅子上；
  • * p：设某个人当前下标为 \(i\)，顺时针移动到 \(pi\) 对应的椅子上；如果有多个人尝试坐到同一个椅子上，移动距离小的人坐，后面的人出局；

\(n,q\le 5\times 10^5\)

先把下标转换成从 \(0\) 开始。如果 \(p\) 和 \(n\) 互质，那么显然不会有人出局。然后可以归纳的证明任意时刻场上的人总是形成一个公差为 \(n\) 的因数的等差数列。因此假设场上的人组成的集合为 \(\{(tx+a)\bmod n\mid x\in [0,\frac{n}{t})\}\)，那么加法等价于给 \(a\) 做模 \(n\) 意义的加法，乘法等价于给 \(x\) 做模 \(\frac{n}{t}\) 意义的乘法。发现出现合并的充要条件是 \(\gcd(\frac{n}{t},p)>1\)，此时 \(t\) 变为 \(t\times \gcd(\frac{n}{t},p)\)，因此一次合并人数至少减小一半，因此合并的轮数不会超过 \(O(\log n)\) 次。

每次暴力重构后记录初始的 \(a\)，然后维护 \(k,a'\) 表示刚重构完时坐在 \(tx+a\) 位置的人移动到了 \(tkx+a'\)。直接维护即可，查询时用 exgcd 求一下逆元。

代码 
 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N = 5e5 + 10;
const int LOGN = 22;

struct myPair {
    int id, dis;
    inline myPair(int _id = 0, int _d = 0) : id(_id), dis(_d) {}
    inline bool operator<(const myPair &b) const {
        return dis < b.dis;
    }
    inline myPair operator+(int x) const { return (myPair){id, x}; }
};

inline void gmin(myPair &a, myPair b) {
    if(a.id == 0) a = b;
    else if(b < a) a = b;
}

int n, q;
myPair id[LOGN][N]; int nn;
int pa[LOGN];

int t = 1, k = 1, a = 0;
void build(int x, int d) {
    ++nn;
    for(int i = 0; i < n / t; i++) {
        int p0 = (t * i + pa[nn - 1]) % n;
        int p1 = (t * (k * i % n) % n + a) * x % n;
        int p2 = (t * (k * i % n) % n + a) % n;
        gmin(id[nn][p1], id[nn - 1][p0] + (p1 + n - p2) % n);
    }
    k = 1; a = a * x % n;
    t = t * d; pa[nn] = a;
}

void exgcd(int a, int b, int &x, int &y) {
    if(b == 0) return x = 1, y = 0, void();
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}
int getinv(int p, int mod) {
    int x, y;
    exgcd(p, mod, x, y);
    return (x % mod + mod) % mod;
}

signed main() {

    // freopen("chair.in", "r", stdin);
    // freopen("chair.out", "w", stdout);

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    id[nn][0] = {n, 0};
    for(int i = 1; i <= n; i++) id[nn][i] = {i, 0};
    pa[nn] = 0;
    while(q--) {
        char op; int x; cin >> op >> x;
        if(op == '+') {
            a = (a + x) % n;
        } else if(op == '*') {
            int d = __gcd(x, n / t);
            if(d == 1) {
                k = k * x % (n / t); a = a * x % n;
            } else {
                build(x, d);
            }
        } else if(op == '?') {
            x %= n;
            if(x % t != a % t) cout << -1 << '\n';
            else {
                x = (x - a + n) % n / t;
                cout << id[nn][(t * (x * getinv(k, n / t)) + pa[nn]) % n].id << '\n';
            }
        } else {
            for(int xx = 1; xx <= n; xx++) { x = xx % n;
                if(x % t != a % t) cout << -1 << ' ';
                else {
                    x = (x - a + n) % n / t;
                    cout << id[nn][(t * (x * getinv(k, n / t)) + pa[nn]) % n].id << ' ';
                }
            }
            cout << endl;
        }
    }

    return 0;
}

T4

给你一个长为 \(n\) 的排列，定义一次操作为选择两个不同的位置，将它们的值进行交换。问你有多少个长为 \(k\) 的操作序列可以把原排列变成单位排列。

\(n\le 30,~k\le 50,~T\le 10^4\)

把排列的置换环拿出来，发现交换两个数等价于置换环的合并和分裂。不难发现我们只关心置换环长度组成的可重集，这样不同的可重集数量是分拆数，在 \(n=30\) 只有 \(5604\) 个。

于是爆搜一遍做完了。时间复杂度 \(O\big(kn^2p(n)\big)\)。

代码 
  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
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<iostream>
#include<unordered_map>
#include<random>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 32;
const int MOD = 1e9 + 7;
const int S = 5700;

inline void add(int &a, int b) { a += b; (a >= MOD) && (a -= MOD); }

int n, k, t;
mt19937_64 rng((random_device){}());
ull w[N];

ll pw[N][N], inv[N], fact[N], ifact[N];

struct Node {
    ull cnt[N];
    inline Node() { for(int i = 0; i < N; i++) cnt[i] = 0; }
    inline ull &operator[](int index) { return cnt[index]; }
    inline const ull &operator[](int index) const { return cnt[index]; }
    inline ull hash() {
        ull res = 0;
        for(int i = 1; i <= n; i++) res += cnt[i] * w[i];
        return res;
    }
    inline ll count() {
        ll res = ifact[n];
        for(int i = 1; i <= n; i++) res = res * fact[cnt[i]] % MOD;
        for(int i = 1; i <= n; i++) res = res * pw[i][cnt[i]] % MOD;
        return res;
    }
};

Node s[5700]; int nn;
unordered_map<ull, int> mp;

void dfs(int pre, int sum, Node v) {
    if(sum == n) {
        s[++nn] = v;
        mp[v.hash()] = nn;
        return;
    }
    for(int i = pre; sum + i <= n; i++) {
        v[i]++;
        dfs(i, sum + i, v);
        v[i]--;
    }
}

int f[S], g[S];

int main() {

    for(int i = 1; i < N; i++) {
        pw[i][0] = 1;
        for(int j = 1; j < N; j++) pw[i][j] = pw[i][j - 1] * i % MOD;
    }
    inv[1] = fact[0] = ifact[0] = 1;
    for(int i = 2; i < N; i++) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    for(int i = 1; i < N; i++) fact[i] = fact[i - 1] * i % MOD;
    for(int i = 1; i < N; i++) ifact[i] = ifact[i - 1] * inv[i] % MOD;

    cin >> n >> k >> t;
    for(int i = 1; i <= n; i++) w[i] = rng();

    dfs(1, 0, (Node){});

    f[1] = 1;
    for(int i = 1; i <= k; i++) {
        for(int j = 1; j <= nn; j++) {
            Node u = s[j];
            if(!f[j]) continue;
            for(int x = 1; x <= n; x++) {
                if(!u[x]) continue;
                int w1 = u[x];
                u[x]--;
                for(int y = x; y <= n; y++) {
                    if(!u[y]) continue;
                    int w2 = u[y]; if(x == y) w2 = (ll)w2 * 500000004 % MOD;
                    u[y]--;
                    u[x + y]++;
                    add(g[mp[u.hash()]], (ll)f[j] * (x * y) % MOD * w1 % MOD * w2 % MOD);
                    u[x + y]--;
                    u[y]++;
                }
                u[x]++;
            }
            for(int x = 1; x <= n; x++) {
                if(!u[x]) continue;
                u[x]--;
                for(int y = 1; 2 * y <= x; y++) {
                    u[y]++;
                    u[x - y]++;
                    add(g[mp[u.hash()]], (ll)f[j] * x % MOD * (x == y << 1 ? 500000004 : 1) % MOD * (u[x] + 1) % MOD);
                    u[y]--;
                    u[x - y]--;
                }
                u[x]++;
            }
        }
        for(int j = 1; j <= nn; j++) f[j] = g[j], g[j] = 0;
    }

    while(t--) {
        Node u;
        static int p[N], vis[N];
        for(int i = 1; i <= n; i++) cin >> p[i], vis[i] = 0;
        for(int i = 1; i <= n; i++) {
            if(vis[i]) continue;
            vis[i] = 1; int sz = 1;
            for(int j = p[i]; j != i; j = p[j]) vis[j] = 1, sz++;
            u[sz]++;
        }
        cout << (ll)f[mp[u.hash()]] * u.count() % MOD << '\n';
    }

    return 0;
}