100 + 100 + 0 + 60, rk 23

被学弟爆踩了捏。

A

傻呗数学结论题。

考虑对称轴的性质,我们只需要考虑右半边的即可。

那么显然就是让我们找一个最小的 t 使得 t\times \alpha\bmod 180= 0

直接算即可。

void solve() {
    ll n,m;read(n,m);
    ll ans = 180 * m / __gcd(180 * m,n) - 2;
    printf("%lld\n",ans);
}

B

考虑这个加法可以如下实现:

n = 1 << n;
int add(int x,int y) {
    x += y;
    while (x & n) x ^= n,++x;
    return x;
}

然后乘法实际上就是暴力相加,就做完了。

注意 IO 速度即可,时间复杂度 \mathcal{O}(2 ^{2t}\times t)

const int N = 5e3 + 10;
int n,t,ans[N][N];

int add(int x,int y) {
    x += y;
    while (x & n) x ^= n,++x;
    return x;
}

inline void writ(int x) {
    //if (!x) return ;
    if (x >= 10) writ(x/10);
    putchar(x % 10 + '0');
}

signed main() {
    //FO(inp)
    read(t);n = 1 << t;
    //printf("%d\n",((1 << (t)) - 1));
    for (int i = 0;i < n;++i) putchar('0'),putchar(' ');
    puts("");
    for (int i = 1;i < n;++i) {
        //int i = 2;
        int now = 0;
        putchar('0'),putchar(' ');
        for (int j = 1;j < n;++j) {
            now = add(now,i);
            writ(now);putchar(' ');
        }
        puts("");
    }
    return 0;
}

C

人类智慧博弈题!暂时搁置。

D

我们先用一个经典 trick,一般这种置换都是需要我们先在 i\rightarrow p_i 之间建边,那么建出来的图必然由若干个环构成。

接下来我们考虑,这个求 pm 层置换本质上就是一个点在环上走 m 步。那么直到这里我们就可以在 \mathcal{O}(n) 的时间内解决本题的第一部分了。

本题的第二部分在于,我们需要把每个 msiz_x 取模。而这个过程如果我们暴力做的话实际上是 \mathcal{O}(n\log m) 的,考虑优化,我们发现实际上不同的环长个数是在 \Theta(\sqrt n) 级别的(这个显然可以通过构造若干个长度构成等差数列的环来实现)而且我们整个取模的过程可以通过压位优化,所以最终的复杂度就可以做到 \mathcal{O}(\sqrt n \frac{\log m}{10})(题解里的压 18 位我好像寄了,最终只压了 10 位,不过影响不大)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define int ll
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define pii pair<int,int>
#define mp make_pair

template <typename T> inline void read(T &t) {
    int v = getchar();T f = 1;t = 0;
    while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
    while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
    t *= f;
}
template <typename T,typename... Args> inline void read(T &t,Args&... args) {
    read(t);read(args...);
}

const ll mod = 998244353;
const double eps = 1e-10;
const int N = 2e6 + 10;
const ll lim = 1e15;
int n,dfn[N],c[N],cnt,siz[N],num,a[N],ans[N],len,M[N],mo[N],p10[N];
ll m,maxx;
char s[N];
int st[N],top;
bool ins[N];
vector <int> G[N],poi[N],buc;

void dfs(int x) {
    st[++top] = x;dfn[x] = ++cnt;
    for (auto y : G[x]) {
        if (!dfn[y]) {
            dfs(y);
        } else {
            int p;c[x] = ++num;
            while (top){
                p = st[top--];c[p] = num;
                poi[num].push_back(p);++siz[num];
            }
            buc.push_back(siz[num]);
            reverse(poi[num].begin(),poi[num].end());
        }
    }
}
signed main() {
    read(n);
    for (int i = 1;i <= n;++i) read(a[i]),G[i].push_back(a[i]);
    for (int i = 1;i <= n;++i) if (!dfn[i]) dfs(i);
    scanf("%s",s+1);
    len = strlen(s + 1);

    sort(buc.begin(),buc.end());
    buc.erase(unique(buc.begin(),buc.end()),buc.end());
    p10[0] = 1;
    for (int i = 1;i <= 12;++i) p10[i] = p10[i-1] * 10;
    for (int l = 1,r = 1;l <= len;l = r + 1) {
        r = min(l + 11,len);
        ll tmp = 0;
        for (int j = l;j <= r;++j) tmp = tmp * 10 + s[j] - '0';
        for (auto x : buc) M[x] = (M[x] * p10[r-l+1] + tmp) % x;
    }
    for (int j = 1;j <= n;++j) {
        for (ll k = 0;k < siz[j];++k) {
            m = M[siz[j]];
            ans[poi[j][k]] = poi[j][(k + m) % siz[j]];
        }
    }
    for (int i = 1;i <= n;++i) printf("%lld ",ans[i]);
    return 0;
}
文章目录