T1 小 L 的数列

1 记录

考场上推出来了

没判 $ n < q $ 难受

2 Solution

显然，每个 $ f_i $ 都是等于下面的试子
$$
\prod_{i=1}^k f_i^{b_i}
$$
也就说，我们可以求 $b_i$

根据费马小定理
$$
a ^ {p -1 } \equiv 1 \pmod p
$$
则显然
$$
\begin{align}
a ^ {k \pm (p – 1)} & \equiv a ^ k \pmod p \\
a ^ {k \bmod (p – 1) } & \equiv a ^ k \pmod p
\end{align}
$$
即指数应当对 $ p – 1 $ 取模

显然
$$
f_{a’,b’} = \sum_{i = 1}^k f_{a’ – i,b’} \times a_i
$$
其中 $b’$ 表示求 $b_{b’}$

矩阵优化即可

3 Source

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

const int N = 210;
const int mod = 998244353;

inline 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;
}

inline int add( int a, int b, const int mod = mod ) {
    int t = a + b;
    return t >= mod? t - mod: t;
}
inline int mul( int a, int b, const int mod = mod ) {
    return ( 1LL * a * b ) % mod;
}

int n, m, ans = 1;
int b[N], f[N];

struct matrix {
    int f[N][N];
    matrix( int tmp = 0 ) {
        memset( f, 0, sizeof(f) );
        if( tmp != 0 ) {
            for( int i = 0; i <= 200; i++ ) 
                f[i][i] = tmp;
        }
    }
    int* operator[] ( int now ) { return f[now]; }
    matrix operator* ( matrix b )  {
        matrix res;
        for( int i = 1; i <= m; i++ ) {
            for( int j = 1; j <= m; j++ ) {
                for( int k = 1; k <= m; k++ ) {
                    res[i][j] = add( res[i][j], mul( this -> f[i][k], b[k][j], mod - 1 ), mod - 1 );    
                }
            }
        }
        return res;
    }
} a, t;

matrix ksm( matrix a, int p ) {
    matrix res(1);
    while(p) {
        if( p & 1 ) 
            res = res * a;
        a = a * a;
        p >>= 1;
    }
    return res;
}

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

matrix miao( matrix a, matrix t ) {
    matrix res;
    for( int i = 1; i <= m; i++ ) {
        for( int j = 1; j <= m; j++ ) {
            res[1][i] = add( res[1][i], mul( a[1][j], t[j][i] , mod - 1 ), mod - 1 );
        }
    }
    return res;
}

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

    n = read(), m = read();
    for( int i = 1; i <= m; i++ ) {
        b[i] = read();
    }
    for( int i = 1; i <= m; i++ ) {
        f[i] = read();
    }

    if( n <= m ) {
        printf( "%d", f[n] );
        return 0;
    }

    for( int i = 1; i <= m; i++ ) {
        t[i][1] = b[i]; 
        if( i != 1 ) 
            t[i - 1][i] = 1;
    }

    matrix tmp = ksm( t, n - m );
    for( int i = 1; i <= m; i++ ) {
        a[1][i] = 1;
        a[1][i - 1] = 0;
        ans = mul( ans, ksm( f[ m - i + 1 ], miao(a, tmp)[1][1] ) );
    }

    printf( "%d\n", ans );

    fclose(stdin);
    fclose(stdout);
    return 0;
}

T2 梦境

1 记录

别说了，考场上全在肝 T1

2 Solution

网上太多的，这题都出烂了

先将梦境转折点排序，然后按左端点排序所有区间，将所有梦境转折点尽可能匹配靠左的区间即可

贪心正确性显然，不做证明

3 Source

#include <cstdio>

#include <queue>
#include <algorithm>

const int N = 2e5 + 1e4;

int n, m, ans;
int t[N];

struct seq {
    int left, rig;
    bool operator< ( const seq b )const { return this -> rig > b.rig; }
} a[N];

std::priority_queue<seq> q;

bool cmp_int( int a, int b ) { return a < b; }
bool cmp_seq( seq a, seq b ) { return a.left < b.left; }

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

    scanf( "%d%d", &n, &m );
    for( int i = 1; i <= n; i++ ) {
        scanf( "%d%d", &a[i].left, &a[i].rig );
    }
    for( int i = 1; i <= m; i++ ) {
        scanf( "%d", &t[i] );
    }

    std::sort( a + 1, a + n + 1, cmp_seq );
    std::sort( t + 1, t + m + 1, cmp_int );

    int p = 1;
    for( int i = 1; i <= m; i++ ) {
        while( a[p].left <= t[i] && p <= n )
            q.push( a[p] ), p ++;
        while( !q.empty() ) {
            seq tmp = q.top();
            q.pop();
            if( tmp.left <= t[i] && tmp.rig >= t[i] ) {
                ans ++;
                break;
            }
        }
    }

    printf( "%d", ans );

    fclose(stdin);
    fclose(stdout);
    return 0;
}

T3 树

1 记录

不说了

2 Solution

这东西我调了一整天

先想其在一条链上，我们将问题直接转化到序列上

从 $[1,l]$中 到 $[r,n]$中 显然是不可达的

我们可以把的转化到二维平面上，即 $x$ 坐标 $[1,l]$ ，$y$ 坐标 $[r,n]$ 的矩形

然后依次添加，就是一道裸的矩形面积并问题，扫描线就行

但是在树上呢？

先用 DFN 序转化到数列上

若 $(x,y)$ 不是父子关系照上

若 $(x,y)$ 为父子关系，$x$ 为父亲的情况下， $y$ 的子树不可到达整棵树除 $x$ 包含 $y$ 的子树的子树

然后但序列上的状况来做即可

3 Source

#include <cstdio>

#include <algorithm>

inline 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;
}

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

const int N = 1e5 + 10;

int n, m, scnt;
long long ans;

// Edge Start 
struct edge {
    int to, next;
} e[N << 2];
int ehead[N << 1], ecnt;
inline void add_edge( int now, int to ) {
    ecnt ++;
    e[ecnt].to = to;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// Edge End

// Segment Tree Start 
int tree[N << 2], lazy[N << 2];

inline void calc( int now, int left, int rig ) {
    if( lazy[now] ) 
        tree[now] = ( rig - left + 1 );
    else if( rig - left == 0 ) 
        tree[now] = 0;
    else 
        tree[now] = tree[ now << 1 ] + tree[ now << 1 | 1 ];
}

inline void pushup( int now, int left, int rig ) {
    if( lazy[now << 1] && lazy[ now << 1 | 1 ] ) {
        int tmp = Min( lazy[now << 1], lazy[ now << 1 | 1 ] );
        lazy[now] = tmp;
        lazy[ now << 1 ] -= tmp; 
        lazy[ now << 1 | 1 ] -= tmp; 
        int mid = ( left + rig ) >> 1;
        calc( now << 1, left, mid );
        calc( now << 1 | 1, mid + 1, rig );
    }
}

inline void pushdown( int now, int left, int rig ) {
    if( lazy[now] ) {
        int mid = ( left + rig ) >> 1;
        lazy[ now << 1 ] += lazy[now];
        lazy[ now << 1 | 1 ] += lazy[now];
        calc( now << 1, left, mid );
        calc( now << 1 | 1, mid + 1, rig );
        lazy[now] = 0;
        calc( now, left, rig );
    }
}

void query_add( int from, int to, int val, int now, int left, int rig ) {
    if( from <= left && rig <= to ) {
        lazy[now] += val;
        calc( now, left, rig );
        return ;
    }
    int mid = ( left + rig ) >> 1;
    pushdown( now, left, rig );
    if( from <= mid )
        query_add( from, to, val, now << 1, left, mid );
    if( to > mid )
        query_add( from, to, val, now << 1 | 1, mid + 1, rig );
    pushup( now, left, rig );
    calc( now, left, rig );
}
// Segment Tree End

// Heavy-Light Decompostion Start
int fa[N], fir[N], last[N], son[N], mson[N], top[N], cnt;
void dfs1( int now ) {
    fir[now] = ++ cnt; son[now] = 1;
    for( int i = ehead[now]; i; i = e[i].next ) {
        if( e[i].to == fa[now] ) 
            continue;
        fa[ e[i].to ] = now;
        dfs1( e[i].to );
        son[now] += son[ e[i].to ];
        if( son[ mson[now] ] < son[ e[i].to ] ) 
            mson[now] = e[i].to;
    }
    last[now] = cnt;
}

void dfs2( int now ) {
    if( top[now] == 0 ) 
        top[now] = now;
    if( son[now] == 1 ) 
        return ;
    top[ mson[now] ] = top[now];
    dfs2( mson[now] );
    for( int i = ehead[now]; i; i = e[i].next ) {
        if( e[i].to == fa[now] || e[i].to == mson[now] ) 
            continue;
        dfs2( e[i].to );
    }
}

int get_son( int from, int to ) {
    int tmp;
    while( top[from] != top[to] ) {
        tmp = top[from];
        from = fa[ top[from] ];
    }
    if( from == to ) { return tmp; }
    return mson[to];
}
// Heavy-Light Decompostion End

// Seq Start 
struct seq {
    int left, rig, y;
    bool add;
} s[N * 16];
bool cmp( seq a, seq b ) { return a.y < b.y; }

inline void add_seq( int left, int rig, int low, int high ) {
    if( left > rig || low > high ) {
        return ;
    }
    int tmp = 0;
    s[ ++ scnt ] = (seq) { left, rig, low, true };
    s[ ++ scnt ] = (seq) { left, rig, high + 1, false };
    s[ ++ scnt ] = (seq) { low, high, left, true };
    s[ ++ scnt ] = (seq) { low, high, rig + 1, false };
    tmp = Min( rig, high ) - Max( low, left ) + 1;
    if( tmp > 0 ) 
        ans -= 1LL * tmp;
}
// Seq End

int main() {
    freopen( "tree.in", "r", stdin );
    freopen( "tree.out", "w", stdout );
    n = read(), m = read();
    for( int i = 1, x, y; i < n; i++ ) {
        x = read(), y = read();
        add_edge( x, y );
        add_edge( y, x );
    }

    dfs1( 3 );
    dfs2( 3 );

    for( int i = 1, x, y; i <= m; i++ ) {
        x = read(), y = read();
        if( fir[y] < fir[x] ) 
            std::swap( x, y );
        if( fir[x] <= fir[y] && fir[y] <= last[x] ) {
            int tmp = get_son( y, x );
            add_seq( fir[y], last[y], 1, fir[x]);
            add_seq( fir[y], last[y], last[x] + 1, n );
            add_seq( fir[y], last[y], fir[x] + 1, fir[tmp] - 1 );
            add_seq( fir[y], last[y], last[tmp] + 1, last[x] );
        }
        else { 
            add_seq( fir[x], last[x], fir[y], last[y] );
        }
    }

    std::sort( s + 1, s + scnt + 1, cmp );

    int p = 1;
    for( int i = 1; i <= n; i++ ) {
        while( s[p].y <= i && p <= scnt ) {
            if( s[p].left != 0 && s[p].rig != 0 )
                query_add( s[p].left, s[p].rig, s[p].add? 1: -1, 1, 1, n );
            p ++;
        }
        ans = ( ans + 1LL * tree[1] );
    }

    printf( "%I64d\n", ( ( 1LL * n * ( n - 1 ) - ans ) >> 1LL ) );
}