T1 锻造 Forging

1 记录

考场上的时候总觉得题目非常的奇妙

因为一直循环下去不就完了吗?

直到后来我的同桌给我指点，原来把 DP 式子当方程解可以了

还是太菜啊

2 Solution

显然，我们设 $ f[i] $ 为到第 $i$ 级的期望的话，则有

设
$$
f[i] = f[i – 2] + f[i – 1] + (1 – p) * (f[i] – f[i – 2])
$$
整理得
$$
f[i] = f[i – 2] + \frac{f[i – 1]}{p}
$$
没了

对了，线性求逆元才能过

3 Source

#include <cstdio>

inline int Min( int a, int b ) { return a < b? a: b; } 

const int N = 1e7 + 1e2;
const int mod = 998244353;

inline int add( int a, int b ) { 
    if( a + b > mod )
        return a + b - mod;
    return a + b;
}
inline int mul( int a, int b ) { return ( 1LL* a * b ) % mod; }

int n, a, bx, by, cx, cy, p;
int b[N], c[N], f[N], inv[N];

int main() {
    freopen( "forging.in", "r", stdin );
    freopen( "forging.out", "w", stdout );

    inv[1] = 1;
    for( int i = 2; i <= (int)(1e7); i++ )
        inv[i] = mul( mod - ( mod / i ), inv[ mod % i ] );


    scanf( "%d%d", &n, &a );    
    scanf( "%d%d%d%d%d", &bx, &by, &cx, &cy, &p );

    b[0] = by + 1; c[0] = cy + 1;
    for( int i = 1; i < n; i++ ) {
        b[i] = ( 1LL * b[ i - 1 ] * bx + by ) % p + 1;
        c[i] = ( 1LL * c[ i - 1 ] * cx + cy ) % p + 1;
    }

    f[0] = a;
    f[1] = add( f[0], mul( mul( f[0], c[0] ), inv[ Min( c[0], b[0] ) ] ) );

    for( int i = 2; i <= n; i++ ) 
        f[i] = add( f[ i - 2 ], mul( mul( f[ i - 1 ], c[ i - 1 ] ), inv[ Min( c[ i - 1 ], b[ i - 2 ] ) ] ) );

    printf( "%d", f[n] );
}

T2 整除 Division

1 记录

考场上直接快速幂暴力跑路

看出来 CRT 能搞忘记 CRT 了

2 Solution

显然，本题可以转化为以下形式
$$
\begin{cases}
x ^ m \equiv x \mod p_1 \\
x ^ m \equiv x \mod p_2 \\
\cdots \\
x ^ m \equiv x \mod p_c
\end{cases}
$$
其中 $p$ 数列是题目给定的素数

将其中每一个方程的解个个数乘起来便是答案

但是直接暴力做的复杂度是 $ O(T \times \sum_{i = 1}^c p_i \times \log(m)) $

这个复杂度只有 $80\%$ 的分数，后面会 TLE

我们可以每次线性筛 $ x^m \mod p_i $

即

设 $ f(x) = x ^ m \mod p_i $

显然，$f$ 是完全积性函数，线性筛即可

复杂度 $ O(T \times ( \sum_{i = 1}^c p_i + k \times \log(m) )$

其中 $k$ 是 $ p_i $ 的质数个数，卡卡常就过了

值得一提的是，这道题目还有基于原根性质 $ O( T \times c \log (p)) $ 的做法，请自行查找

代码因为卡常非常丑陋，凑活看吧……

3 Source

#include <stdio.h>
#include <string.h>

inline unsigned int read() {
    register char c = 0; register unsigned int now = 0;
    while( c < '0' || c > '9' )
        c = getchar();
    while( c >= '0' && c <= '9' ) {
        now = ( now << 3 ) + ( now << 1 ) + ( c - 48 );
        c = getchar();
    }
    return now;
}

const unsigned int N = 1e4 + 3;
const unsigned int MOD = 998244353;

//inline unsigned int mul( register unsigned int a, register unsigned int b, register unsigned int mod = MOD ) { return ( 1LL * a * b ) % mod; }

unsigned int T, c, m;

inline unsigned int ksm( register unsigned int a, register unsigned int p, register unsigned int mod ) {
    register unsigned int res = 1;
    while(p) {
        if( p & 1 ) 
            res = res * a % mod;
        a = a * a % mod;
        p >>= 1;
    }
    return res;
}

unsigned int tmp_pcnt, real_pcnt;
unsigned int pri[N], f[N];
bool vis[N];
inline void pre( register unsigned int mod ) {
    tmp_pcnt = 0;
    for( register unsigned int i = 1; i <= real_pcnt; i++ )
        f[ pri[i] ] = ksm( pri[i], m, mod );

    for( register unsigned int i = 2; i < mod; i++ ) {
        if( vis[i] == false ) 
            ++ tmp_pcnt;
        for( register unsigned int j = 1; j <= tmp_pcnt; j++ ) {
            if( pri[j] * i > mod )
                break;

            f[ i * pri[j] ] = ( f[i] * f[ pri[j] ] ) % mod;

            if( i % pri[j] == 0 ) 
                break;
        }
    }
}

inline void get_pri() {
    for( register unsigned int i = 2; i <= 10000; i++ ) {
        if( vis[i] == false ) 
            pri[ ++ real_pcnt ] = i;
        for( register unsigned int j = 1; j <= real_pcnt; j++ ) {
            if( pri[j] * i > 10000 )
                break;
            vis[ i * pri[j] ] = true;
            if( i % pri[j] == 0 ) 
                break;
        }
    }
}

int main() {
    freopen( "division.in", "r", stdin );
    freopen( "division.out", "w", stdout );

    get_pri();
    f[1] = 1;

    read(); T = read();

    while( T-- ) {
        register unsigned int ans = 1, cnt;
        c = read(), m = read();

        register unsigned int tmp;
        for( register unsigned int i = 1; i <= c; i++ ) {
            tmp = read();

            pre( tmp );
            cnt = 2;
            for( register unsigned int j = 2; j < tmp; j++ ) {
                if( f[j] - j == 0 ) 
                    cnt ++;
            }
            if( cnt != 0 ) 
                ans = ( 1LL * ans * cnt ) % MOD;
        }
        printf( "%d\n", ans );
    }
}

T3 欠钱 Money

1 记录

考场胡出来了前 $ 60\% $ 的数据结果没时间调了，一分未得……

2 Solution

题目有多种解法，参考本目录下的 官方 Soltion.pdf

这里只讲述 LCT 解法

复杂度不想讲了

注意 LCT 求 LCA 的方法

先 access(a) 再 access(b) 最后 splay 到的节点即为 $lca(a,b)$

后面就是 LCT 标准操作

3 Source

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cstring>

#include <algorithm>

inline int Min( register int a, register int b ) { return a < b? a: b; }

int read() {
    register char c = 0; register int now = 0;
    while( c < '0' || c > '9' )
        c = getchar();
    while( c >= '0' && c <= '9' ) {
        now = ( now << 3 ) + ( now << 1 ) + ( c - 48 );
        c = getchar();
    }
    return now;
}

int st[100001], stcnt;
void write( register int a, register char end = 0 ) {
    while(a) {
        st[ ++ stcnt ] = a % 10;
        a /= 10;
    }
    if( stcnt == 0 )
        putchar( '0' );
    while( stcnt ) {
        putchar( st[stcnt] + '0' );
        stcnt --;
    }
    putchar( end );
}

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m, last_ans;

inline void get_real( register int &a ) { a = ( a + last_ans ) % n + 1; }

//struct _fa {
    int fa[N];
    void init( register int now ) { for( register int i = 1; i <= now; i++ ) fa[i] = i; }
//    int& operator[] ( register int now ) { return fa[now]; }
    int get_fa( register int now ) {
        if( fa[now] == now ) 
            return now;
        return fa[now] = get_fa( fa[now] );
    }
//}fa;


struct node {
    int son[2], fa, val, min;
    bool rev;
} tree[N];

inline bool get_son( register int now ) { return tree[ tree[now].fa ].son[1] == now; }

inline bool not_root( register int now ) { return tree[ tree[now].fa ].son[0] == now || tree[ tree[now].fa ].son[1] == now ; }

inline void push_up( register int now ) {
    tree[now].min = tree[now].val;
    tree[now].min = Min( tree[ tree[now].son[0] ].min , Min( tree[ tree[now].son[1] ].min, tree[now].val ) );
}

inline void get_re( register int now ) {
    std::swap( tree[now].son[0], tree[now].son[1] );
    tree[now].rev ^= 1;
}

inline void push_down( register int now ) {
    if( tree[now].rev ) {
        if( tree[now].son[0] ) 
            get_re( tree[now].son[0] );
        if( tree[now].son[1] ) 
            get_re( tree[now].son[1] );
        tree[now].rev = 0;
    }
}

inline void push_all( register int now ) {
    while(now) {
        if( not_root(now) == false ) {
            push_down(now);
            break;
        }
        st[ ++ stcnt ] = now;
        now = tree[now].fa;
    }
    while( stcnt ) {
        push_down( st[stcnt] );
        stcnt --;
    }
    stcnt = 0;
//    if( not_root(now) ) 
//        push_all( tree[now].fa );
//    push_down(now);
}

inline void rotate( register int now ) {
    register int tmp = tree[now].fa;
    register bool kind = get_son(now);
    if( not_root(tmp) ) 
        tree[ tree[tmp].fa ].son[ get_son(tmp) ] = now;
    tree[now].fa = tree[tmp].fa; 
    tree[tmp].son[kind] = tree[now].son[ kind ^ 1 ]; tree[ tree[tmp].son[kind] ].fa = tmp;
    tree[tmp].fa = now; tree[now].son[ kind ^ 1 ] = tmp;
    push_up(tmp); push_up(now);
}

inline void splay( register int now ) {
    push_all(now);
    while( not_root(now) ) {
        register int tmp = tree[now].fa;
        if( not_root( tmp ) ) 
            rotate( get_son(tmp) == get_son(now)? tmp: now ); 
        rotate(now);
    }
}

inline int access( register int now ) {
    register int res = 0;
    for( register int tmp = 0; now; now = tree[ tmp = now ].fa ) 
        splay(now), tree[now].son[1] = tmp, push_up(now), res = now;
    return res;
}

inline void makeroot( register int now ) {
    access(now); splay(now); get_re(now);
}

inline void link( register int from, register int to, register int val ) {
    splay(from);
    tree[from].fa = to;
    tree[from].val = val;
    tree[from].min = Min( tree[from].min, tree[from].val );
}

inline int ask( register int from, register int to ) {
    register int res = 0;
    access(to);
    if( access(from) == to ) {
        makeroot(to);
        access(from);
        splay(to);
        res = tree[ tree[to].son[1] ].min;
        makeroot( get_fa(to) );
    }
    return res;
}

int main() {
    freopen( "money.in", "r", stdin );
    freopen( "money.out", "w", stdout );

    last_ans = 0; tree[0].min = INF;
    n = read(); m = read();
    init(n);
    for( register int i = 1; i <= m; i++ ) {
        register int op = read();
        if( op == 0 ) {
            register int a = read(), b = read(), c = read();    
            get_real(a), get_real(b), get_real(c);
            fa[a] = b;
            link( a, b, c );
        }
        else {
            register int a = read(), b = read();
            get_real(a), get_real(b);
            if( get_fa(a) != get_fa(b) ) 
                last_ans = 0;
            else
                last_ans = ask( a, b );
            write( last_ans, '\n' );
        }
    }
}