Description

Link.

求 $\begin{Bmatrix}n \\ m\end{Bmatrix}\bmod2$

Solution

求

$$ \begin{aligned} \begin{Bmatrix}n \\ m\end{Bmatrix}\bmod2 &=\left(\begin{Bmatrix}n-1 \\ m-1\end{Bmatrix}+m\begin{Bmatrix}n-1 \\ m\end{Bmatrix}\right)\bmod2 \\ &=\begin{cases} \begin{Bmatrix}n-1 \\ m-1\end{Bmatrix}\bmod2,m\equiv0\space(\operatorname{mod}2) \\ \left(\begin{Bmatrix}n-1 \\ m-1\end{Bmatrix}+\begin{Bmatrix}n-1 \\ m\end{Bmatrix}\right)\bmod2,m\equiv1\space(\operatorname{mod}2) \end{cases} \end{aligned} $$

$m\equiv1\space(\operatorname{mod}2)$ 的情况为组合数的递推。

转化一下，把填表转移换成刷表，即

• 当 $m\equiv0\space(\operatorname{mod}2)$ 时，$\begin{Bmatrix}n \\ m\end{Bmatrix}$ 转移到 $\begin{Bmatrix}n+1 \\ m+1\end{Bmatrix}$。
• 当 $m\equiv1\space(\operatorname{mod}2)$ 时，$\begin{Bmatrix}n \\ m\end{Bmatrix}$ 转移到 $\begin{Bmatrix}n+1 \\ m+1\end{Bmatrix}$ 和 $\begin{Bmatrix}n+1 \\ m\end{Bmatrix}$。

那么这个题目就转化成了在表格上 $(0,0)$ 走到 $(n,m)$ 的路径条数 $\operatorname{mod}2$ 问题。

两种情况都可以转移到 $\begin{Bmatrix}n+1 \\ m+1\end{Bmatrix}$，为了方便起见，我们定义这种情况为向右上转移，把 $\begin{Bmatrix}n+1 \\ m\end{Bmatrix}$ 定义为向上转移。

因为我们转移只能向上或右上走，所以只会走 $n$ 步，其中 $m$ 次向右上转移，$n-m$ 次向右转移。

我们一共有 $\lfloor\frac{m+1}{2}\rfloor$ 次机会向右转移（只能从奇数走）。

相当于我们现在需要把转移的过程分成 $n-m$ 段，每一段的内部全部都是向右上转移，这样我们才能到达 $(n,m)$。

用盒子与球的语言来描述，就是一共就有 $n-m+\lfloor\frac{m+1}{2}\rfloor$ 个球（这里理解起来其实特别麻烦）（不过只是对于我这种组合差的人），分成 $\lfloor\frac{m+1}{2}\rfloor$ 段，隔板即可。

于是 $\begin{Bmatrix}n \\ m\end{Bmatrix}\bmod2={n-m+\lfloor\frac{m+1}{2}\rfloor-1\choose\lfloor\frac{m+1}{2}\rfloor-1}\bmod2$。

关于组合数奇偶性，我这篇博客里写过，再贴上来：

结论：$\dbinom{n}{m}\equiv0\space(\operatorname{mod}2)$ 当且仅当 $n\operatorname{bitand}m=m$。

证明（也许不是特别严谨）：我们可以知道：

$$ {n\choose m}={\lfloor\frac{n}{2}\rfloor\choose\lfloor\frac{m}{2}\rfloor}\times{n\bmod 2\choose m\bmod2}={\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor\choose\lfloor\frac{\lfloor\frac{m}{2}\rfloor}{2}\rfloor}\times {\lfloor\frac{n}{2}\rfloor\bmod2\choose\lfloor\frac{m}{2}\rfloor\bmod2}\times{n\bmod 2\choose m\bmod2}=\cdots $$

我们发现：

$$ {\lfloor\frac{\lfloor\frac{\lfloor\frac{n}{2}\rfloor}{2}\rfloor}{\cdots}\rfloor\choose\lfloor\frac{\lfloor\frac{\lfloor\frac{m}{2}\rfloor}{2}\rfloor}{\cdots}\rfloor} $$

这一坨，就是在一直进行二进制移位，$\operatorname{shr}1$。

那么我们可以得出一个结论：如果对于我们记 $(n)_{k}$ 表示 $n$ 在二进制意义下的第 $k$ 位。$(n)_{k}\in[0,1]$

那么对于 $\forall i$，有 $(n)_{i}=0$ 且 $(m)_{i}=1$，那么 $\dbinom{n}{m}\equiv0\space(\operatorname{mod} 2)$。

所以 $n\operatorname{bitand}m=m$，证毕。

答案显然。

#include <cstdio>

int N, M;

int main () {
    int TC; scanf ( "%d", &TC ); while ( TC -- > 0 ) {
        scanf ( "%d%d", &N, &M );
        if ( ! N && ! M )    puts ( "1" );
        else if ( ! N || ! M || N < M )    puts ( "0" );
        else if ( ( ( N - M + ( ( M + 1 ) >> 1 ) - 1 ) & ( ( ( M + 1 ) >> 1 ) - 1 ) ) == ( ( ( M + 1 ) >> 1 ) - 1 ) )    puts ( "1" );
        else    puts ( "0" );
    }
    return 0;
}

Craft

Prob. 1

Desc. & Link.

有想法。

printf( "nan" );

Prob.2

Desc. & Link.

没读懂

Prob. 3

Desc. & Link.

定义 $f_{i,j,0/1}$ 表示个寂寞。

$$ f_{i,i,0/1}=|a_{i}|\times I $$

$$ f_{i,j,0}=\min\{f_{i+1,j,0}+(a_{i+1}-a_{i})\times(I-j+i),f_{i+1,j,1}+(a_{j}-a_{i})\times(I-j+i)\} \\f_{i,j,1}=\min\{f_{i,j-1,1}+(a_{j}-a_{j-1})\times(I-j+i),f_{i,j-1,0}+(a_{j}-a_{i})\times(I-j+i)\} $$

$$ \mathrm{ANS}=\max\{i\times m-\min\{f_{l,r,0/1}\}\} $$

Over.

Prob. 4

Desc. & Link.

转化一下，把 $\texttt{C,T}$ 换成左括号和右括号。

把左括号赋值为 $1$，右括号 $-1$。

把这个 $1/-1$ 序列设为 $A$

那么所有前缀中 $\texttt{C}$ 的个数大于等于 $\texttt{T}$ 的个数即要求前缀和不能出现负数。

询问即求：定义 $P_{i}=\sum_{j=1}^{i}A_{j},S_{i}=\sum_{j=i}^{n}A_{j}$，对于每次询问回答：

$$ \begin{cases}0,\min\{\min\{P_{l,l+1,\cdots,r}\},\min\{S_{l,l+1,\cdots,r}\}\}\ge0 \\ |\min\{\min\{P_{l,l+1,\cdots,r}\},\min\{S_{l,l+1,\cdots,r}\}\}|,\texttt{otherwise}\end{cases}​ $$

这个东西 $\texttt{has been hacked by the Big Sample.}$

一个可能的死亡原因：前缀后缀都要判断可能会引起一些错误。

处理方法：那么先处理前缀，后缀减一下再处理。

（这不是问题）

另一个可能的死亡原因：$\min\{\min\{P_{l,l+1,\cdots,r}\},\min\{S_{l,l+1,\cdots,r}\}\}$ 可能取到多处。

处理方法：。

（这也不是问题）

Algo. 0

W·violence·gy

Algo. 1

莫队，时间复杂度 $\Theta(n\sqrt{n}\log_{2}n)$。

Algo. 2

晓求不得。

Solution

Prob. 4

转化一下成最大子段和，化式子过程懒得写了。

LOC 2020.11.20 - Prob. 1

Desc. & Link.

$C=2^{k}\bmod(a+b+c)$

#include <cstdio>

typedef long long LL;

int A, B, C, K;

int Qkpow( int base, int indx, int mod ){
    int res = 1;
    while( indx ){
        if( indx & 1 )    res = ( LL )res * base % mod;
        base = ( LL )base * base % mod;
        indx >>= 1;
    }
    return res;
}

int main( ){
    int TC; scanf( "%d", &TC ); while( TC -- > 0 ){
        scanf( "%d%d%d%d", &A, &B, &C, &K );
        printf( "%lld\n", ( LL )C * Qkpow( 2, K, A + B + C ) % ( A + B + C ) );
    }
    return 0;
}

LOC 2020.11.20 - Prob. 2

Desc. & Link.

我先行否决 naive 的线段树。

输入暗示连边？

那就连吧。

考虑每一个连通块 $S$，如果连通块是个树，就只能选 $|S|-1$ 个点。

如果存在环，那么每个数都取得到。

那么可以的情况就是询问区间包含的不是一棵树。

#include <cstdio>

const int MAXN = 2e5 + 5;

template<typename _T> _T MIN( const _T x, const _T y ){ return x > y ? y : x; }
template<typename _T> _T MAX( const _T x, const _T y ){ return x > y ? x : y; }

struct pointS{
    int one, ano;
    pointS( int O = 0, int A = 0 ){ one = A; ano = A; }
} pntS[MAXN];

struct starS{
    int to, nx;
    starS( int T = 0, int N = 0 ){ to = T; nx = N; }
} as[MAXN * 2];

int N, K, Q;
int totE;
int firS[MAXN], furS[MAXN], enS[MAXN], mxV[MAXN], mnV[MAXN], vis[MAXN];

void pushEdge( const int u, const int v ){ as[++ totE] = starS( v, firS[u] ); firS[u] = totE; furS[u] ++; }

void DFS( const int u, int &mxVt, int &mnVt, int &edgeS, int &nodeS ){
    mxVt = MAX( mxVt, u ); mnVt = MIN( mnVt, u );
    edgeS += furS[u]; nodeS ++; vis[u] = 1;
    for( int i = firS[u]; i; i = as[i].nx ){
        int v = as[i].to;
        if( vis[v] )    continue;
        DFS( v, mxVt, mnVt, edgeS, nodeS );
    }
}

int main( ) {
    scanf( "%d%d", &N, &K );
    for( int i = 1; i <= K; ++ i ){
        scanf( "%d%d", &pntS[i].one, &pntS[i].ano );
        pushEdge( pntS[i].one, pntS[i].ano );
        pushEdge( pntS[i].ano, pntS[i].one );
    }
    for( int i = 1; i <= N; ++ i )    enS[i] = N + 1;
    for( int i = 1; i <= N; ++ i ){
        if( vis[i] )    continue;
        int mxVt = 1, mnVt = N, edgeS = 0, nodeS = 0;
        DFS( i, mxVt, mnVt, edgeS, nodeS ); edgeS >>= 1;
        if( edgeS == nodeS - 1 )    enS[mnVt] = mxVt;
    }
    for( int i = N - 1; i; -- i )    enS[i] = MIN( enS[i], enS[i + 1] );
    scanf( "%d", &Q );
    while( Q -- > 0 ){
        int queL, queR;
        scanf( "%d%d", &queL, &queR );
        if( enS[queL] > queR )    printf( "Yes\n" );
        else    printf( "No\n" );
    }
    return 0;
}

LOC 2020.11.20 - Prob. 3 / CF396C On Changing Tree

Desc. & Link.

哇哦。

喜闻乐见的 DS 题。

大约是届一下 $\texttt{lazy tag}$ 的思想。

对于一个节点 $u$，只有在路径 $(1,u)$ 上的修改才会产生影响。

这个询问有够简单，差个分即可。

修改就子树加 $x$，再加个 $k$（除根节点）。

树剖，完了。

#include <cstdio>
#define mod ( 1000000007 )

typedef long long LL;

const int MAXN = 3e5 + 5;

template<typename _T>
void read( _T &x ){
    x = 0; char c = getchar( ); _T f = 1;
    while( c < '0' || c > '9' ){ if( c == '-' )    f = -1; c = getchar( ); }
    while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar( ); }
    x *= f;
}

template<typename _T>
void write( _T x ){
    if( x < 0 ){ putchar( '-' ); x = -x; }
    if( x > 9 )    write( x / 10 );
    putchar( x % 10 + '0' );
}

template<typename _T> void swapp( _T &x, _T &y ){ int w = x; x = y; y = w; }

struct starS{
    int to, nx;
    starS( int T = 0, int N = 0 ){ to = T; nx = N; }
} as[MAXN * 2];

struct nodeS{
    int val, add;
    nodeS( int V = 0, int A = 0 ){ val = V; add = A; }
} nodes[MAXN * 4];

int N, M;
int sjc, cnt;
int firS[MAXN], posL[MAXN], posR[MAXN], top[MAXN], son[MAXN], dep[MAXN], fur[MAXN], fa[MAXN];

void pushEdge( const int u, const int v ){ as[++ cnt] = starS( v, firS[u] ); firS[u] = cnt; }

void oneSearch( const int u, const int lst ){
    fa[u] = lst; dep[u] = dep[lst] + 1; fur[u] = 1;
    for( int i = firS[u]; i; i = as[i].nx ){
        int v = as[i].to;
        oneSearch( v, u );
        fur[u] += fur[v];
        if( fur[v] > fur[son[u]] )    son[u] = v;
    }
}

void anotherSearch( const int u, const int nTp ){
    top[u] = nTp; posL[u] = ++ sjc;
    if( son[u] )    anotherSearch( son[u], nTp );
    for( int i = firS[u]; i; i = as[i].nx ){
        int v = as[i].to;
        if( v == son[u] )    continue;
        anotherSearch( v, v );
    }
    posR[u] = sjc;
}

void Spr( const int x, const int l, const int r ){
    if( ! nodes[x].add )    return;
    int mid = ( l + r ) >> 1;
    nodes[x << 1].val = ( nodes[x << 1].val + ( LL )nodes[x].add * ( mid - l + 1 ) % mod ) % mod;
    nodes[x << 1 | 1].val = ( nodes[x << 1 | 1].val + ( LL )nodes[x].add * ( r - mid ) % mod ) % mod;
    nodes[x << 1].add = ( nodes[x << 1].add + nodes[x].add ) % mod;
    nodes[x << 1 | 1].add = ( nodes[x << 1 | 1].add + nodes[x].add ) % mod;
    nodes[x].add = 0;
}

void Upt( const int x ){ nodes[x].val = ( nodes[x << 1].val + nodes[x << 1 | 1].val ) % mod; }

void Modify( const int x, const int l, const int r, const int segL, const int segR, const int segW ){
    if( l > segR || r < segL )    return;
    if( l >= segL && r <= segR ){
        nodes[x].val = ( nodes[x].val + ( LL )segW * ( r - l + 1 ) % mod ) % mod;
        nodes[x].add = ( nodes[x].add + segW ) % mod;
        return;
    }
    int mid = ( l + r ) >> 1;
    Spr( x, l, r );
    Modify( x << 1, l, mid, segL, segR, segW );
    Modify( x << 1 | 1, mid + 1, r, segL, segR, segW );
    Upt( x );
}

int Query( const int x, const int l, const int r, const int segL, const int segR ){
    if( l > segR || r < segL )    return 0;
    if( l >= segL && r <= segR )    return nodes[x].val;
    int mid = ( l + r ) >> 1; Spr( x, l, r );
    return ( Query( x << 1, l, mid, segL, segR ) + Query( x << 1 | 1, mid + 1, r, segL, segR ) ) % mod;
}

int QueryP( int u, int v ){
    int res = 0;
    while( top[u] != top[v] ){
        if( dep[top[u]] < dep[top[v]] )    swapp( u, v );
        res = ( ( res + Query( 1, 1, N, posL[top[u]], posL[u] ) ) % mod + mod ) % mod;
        u = fa[top[u]];
    }
    if( dep[u] >= dep[v] )    swapp( u, v );
    res = ( ( res + Query( 1, 1, N, posL[u], posL[v] ) ) % mod + mod ) % mod;
    return res;
}

int main( ){
    read( N );
    for( int i = 2, lst; i <= N; ++ i ){ read( lst ); pushEdge( lst, i ); }
    oneSearch( 1, 0 ); anotherSearch( 1, 1 );
    read( M );
    while( M -- > 0 ){
        int opt, u, x, k;
        read( opt );
        if( opt == 1 ){
            read( u ); read( x ); read( k );
            Modify( 1, 1, N, posL[u], posL[u], x );
            Modify( 1, 1, N, posL[u] + 1, posR[u], -k );
        }
        else{ read( u ); write( QueryP( 1, u ) ); putchar( '\n' ); }
    }
    return 0;
}

LOC 2020.11.20 - Prob. 4

Desc. & Link.

不想做了。

Part. 1 Stirling Number / FK.

Def. 定义 $\begin{bmatrix}n \\ m\end{bmatrix}$ 表示将 $n$ 个元素分成 $m$ 个环的方案数。

递推式为

$$ \begin{bmatrix}n \\ m\end{bmatrix}=\begin{bmatrix}n-1 \\ m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1 \\ m\end{bmatrix} $$

即考虑已经放好的 $n-1$ 个数，第一种情况是自成环即 $\begin{bmatrix}n-1 \\ m-1\end{bmatrix}$，第二种情况是放在某一个环内，可以放在任意一个已经放好的数前，即 $(n-1)\begin{bmatrix}n-1 \\ m\end{bmatrix}$。

边界为：

$$ \begin{bmatrix}n \\ 0\end{bmatrix}=[n=0] $$

一个性质：

$$ n!=\sum_{i=0}^{n}\begin{bmatrix}n \\ i\end{bmatrix} $$

多项式形式：$\begin{bmatrix}n \\ m\end{bmatrix}$ 为 $f_{n}(x)=\prod_{i=0}^{n-1}(x+i)$ 的 $k$ 次项系数。

Part. 2 Stirling Number / SK.

Def. 定义 $\begin{Bmatrix}n \\ m\end{Bmatrix}$ 表示将 $n$ 个不同的球放进 $m$ 个相同的盒子的方案数。

递推式为

$$ \begin{Bmatrix}n \\ m\end{Bmatrix}=\begin{Bmatrix}n-1 \\ m-1\end{Bmatrix}+m\begin{Bmatrix}n-1 \\ m\end{Bmatrix} $$

意义即前 $n-1$ 个球放进了 $m-1$ 的盒子里，$n$ 就只有一种方法，如果前 $n-1$ 个球放进了 $m$ 个盒子，那么这个球就有 $m$ 种放法。

容斥一下可以得到通项公式（背吧）

$$ \begin{Bmatrix}n \\ m\end{Bmatrix}=\frac{1}{m!}\sum_{i=0}^{m}\left((-1)^{i}{m\choose i}(m-i)^{n}\right) $$

拆完组合数可以卷积 $\texttt{NTT}$ 做，不过咱多项式学得废，就不整了。

Problem. 1 - Junior Julian

模拟模拟模拟摸死 CTR 的母。

考场代码：

#include<cstdio>
namespace solveIt
{
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    write(x/10);
    putchar(x%10+'0');
}
int Q;
int chkyearG(int mon) // 1:run 0:ping
{
    if(((mon%4==0)&&(mon%100!=0))||(mon%400==0))    return 1;
    else    return 0;
}
int chkyearJ(int mon) // 1:run 0:ping
{
    if(mon%4==0)    return 1;
    else    return 0;
}
int chkmontG(int mon,int yea) // 31: big,30: small,28/29: 2
{
    if(yea<0)    yea=-yea,yea--;
    if(mon==1||mon==3||mon==5||mon==7||mon==8||mon==10||mon==12)    return 31;
    else if(mon!=2)    return 30;
    else
    {
        if(chkyearG(yea))    return 29;
        else    return 28;
    }
}
int chkmontJ(int mon,int yea) // 31: big,30: small,28/29: 2
{
    if(yea<0)    yea=-yea,yea--;
    if(mon==1||mon==3||mon==5||mon==7||mon==8||mon==10||mon==12)    return 31;
    else if(mon!=2)    return 30;
    else
    {
        if(chkyearJ(yea))    return 29;
        else    return 28;
    }
}
void Main()
{
    read(Q);
    while(Q--)
    {
        int r;
        read(r);
        int days=1,months=1,years=-4713;
        int flag=0; // 0:Julian,1:Gregorian
        while(true)
        {
            if(years==0)    years=1;
            if(days==1&&months==10&&years==1582)
            {
                if(r<=3)
                {
                    days+=r;
                    break;
                }
                else if(r>3&&r<20)
                {
                    days+=3;
                    r-=3;
                    days=15;
                    days+=r;
                    break;
                }
                else
                {
                    flag=1;
                    days=1;
                    r-=21;
                    months++;
                }
            }
            if(days+r<=(flag?chkmontG(months,years):chkmontJ(months,years)))
            {
                days+=r;
                break;
            }
            days=1;
            r-=(flag?chkmontG(months,years):chkmontJ(months,years));
            months++;
            if(months==13)    months=1,years++;
        }
        if(years>0)    printf("%d %d %d\n",days,months,years);
        else    printf("%d %d %d BC\n",days,months,-years);
    }
}
}
int main()
{
//    freopen("D:/csp-s(windows)/julian/julian3.in","r",stdin);
//    freopen("D:/my.out","w",stdout);
    freopen("julian.in","r",stdin);
    freopen("julian.out","w",stdout);
    solveIt::Main();
    return 0;
}
/*
There are 365 days in a ping year.
There are 366 days in a run year.
There are 4714 ping years in -4713(BC) to 1582
There are 1582 run years in -4713(BC) to 1582
There are 2299622 days in -4713(BC) to 1582
There are 3571 ping years BC
There are 1142 yun years BC
There are 1721387 days in BC
*/

下来重写：

#include <cstdio>

typedef long long LL;

template<typename _T>
void read( _T &x ){
    x = 0; char c = getchar( ); _T f = 1;
    while( c < '0' || c > '9' ){ if( c == '-' )    f = -1; c = getchar( ); }
    while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar(); }
    x *= f;
}

template<typename _T>
void write( _T x ){
    if( x < 0 ){ putchar( '-' ); x = -x; }
    if( x > 9 )    write( x / 10 );
    putchar( x % 10 + '0' );
}

int MonthDays( int x ){
    if( x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12 )    return 31;
    else if( x == 2 )    return 28;
    else    return 30;
}

bool checkRJ( int x ){ return ! ( x % 4 ); }
bool checkRG( int x ){ return ( ( ! ( x % 4 ) ) && ( x % 100 ) ) || ( ! ( x % 400 ) ); }

int Q;

void GetData( LL& dBC, LL& dAJ, LL& dAG, LL& dFK ){
    for( int i = 4712; ~ i; -- i )  dBC += 365 + checkRJ( i );
    dAJ = dBC; dAG = dBC;
    for( int i = 1; i <= 1581; ++ i )    dAJ += 365 + checkRJ( i );
    for( int i = 1; i <= 1582; ++ i )    dAG += 365 + checkRG( i );
    dFK = dAJ + 365;
    for( int i = 1; i <= 9; ++ i )  dAJ += MonthDays( i );
    dAJ += 4;
}

int fuckCTR( int x, int y ){
    if( y < 0 )    ++ y;
    if( x != 2 )    return MonthDays( x );
    if( y <= 1582 ) return MonthDays( x ) + checkRJ( y );
    else    return MonthDays( x ) + checkRG( y );
}

int main( ){
    LL dBC = 0, dAJ = 0, dAG = 0, dFK = 0;
    /*
     * several key time frame:
     * 4713.1.1
     * 1582.10.5~14 ( don't exist )
     * 1582.10.4 Julian Calendar has been fucked
     * 1582.10.15 Gregorian Calendar has been implemented
     * dBC - 1.1.1 (Julian Day)
     * dAJ - 1582.10.15 (Julian Day)
     * dFK - 1583.1.1 (Imagine that the fucking 10 days exist)
     * dAG - 1583.1.1 (the fucking 10 days don't exist(the fucking problem's description))
    */
    GetData( dBC, dAJ, dAG, dFK );
    read( Q ); while( Q -- > 0 ){
        LL R; read( R );
        if( R < dBC ){
            int years = 4713 - R / ( 365 * 4 + 1 ) * 4; R %= ( 365 * 4 + 1 );
            if( R >= 366 ){
            R -= 366; years --;
            if( R >= 365 ){ R -= 365; years --; }
            if( R >= 365 ){ R -= 365; years --; }
            }
            int months = 1;
            while( R - fuckCTR( months, -years ) >= 0 ){ R -= fuckCTR( months, -years ); months ++; }
            int days = R + 1;
            printf( "%d %d %d BC\n", days, months, years );
            continue;
        }
        if( R >= dAJ )    R += 10;
        if( R >= dBC && R < dFK ){
            R -= dBC;
            int years = R / ( 365 * 4 + 1 ) * 4 + 1; R %= ( 365 * 4 + 1 );
            if( R >= 365 ){ R -= 365; years ++; }
            if( R >= 365 ){ R -= 365; years ++; }
            if( R >= 365 ){ R -= 365; years ++; }
            int months = 1;
            while( R - fuckCTR( months, years ) >= 0 ){ R -= fuckCTR( months, years ); months ++; }
            int days = R + 1;
            printf( "%d %d %d\n", days, months, years );
            continue;
        }
        if( R >= dFK ){
            R -= dBC; R += dAG - dFK;
            int years = R / ( 365 * 400 + 24 * 4 + 1 ) * 400 + 1; R %= ( 365 * 400 + 24 * 4 + 1 );
            if( R >= 365 * 100 + 24 ){ R -= 365 * 100 + 24; years += 100; }
            if( R >= 365 * 100 + 24 ){ R -= 365 * 100 + 24; years += 100; }
            if( R >= 365 * 100 + 24 ){ R -= 365 * 100 + 24; years += 100; }
            years += R / ( 365 * 4 + 1 ) * 4; R %= ( 365 * 4 + 1 );
            if( R >= 365 ){ R -= 365; years ++; }
            if( R >= 365 ){ R -= 365; years ++; }
            if( R >= 365 ){ R -= 365; years ++; }
            int months = 1;
            while( R - fuckCTR( months, years ) >= 0 ){ R -= fuckCTR( months, years ); months ++; }
            int days = R + 1;
            printf( "%d %d %d\n", days, months, years );
        }
    }
    return 0;
}

码风飞跃的变化

Problem. 2 - Junior Zoo

把所有数或起来，然后计算需要买哪些饲料，然后统计 $1\texttt{ to }k$ 有哪些位没有被买，记为 $C$ 然后答案就是 $2^{C}-n$。

考场代码：

#include<cstdio>
#include<vector>
namespace solveIt
{
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    write(x/10);
    putchar(x%10+'0');
}
const int MAXN=1e6+5;
int n,m,c,k,a[MAXN],vis[MAXN],fuc[MAXN];
struct ask
{
    int w,s;
    ask(int W=0,int S=0){w=W;s=S;}
}as[MAXN];
void Main()
{
    read(n),read(m),read(c),read(k);
    for(int i=1;i<=n;++i)    read(a[i]),fuc[a[i]]=1;
    for(int i=1;i<=m;++i)    read(as[i].w),read(as[i].s);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
        {
//            printf("FU ");for(int i=1;i<=c;++i)    printf("%d ",vis[i]); puts("");
            if((a[i]>>as[j].w)&1)    vis[as[j].s]=1;//,printf("%d %d %d\n",a[i],as[j].w,as[j].s);
        }
    }
//    for(int i=1;i<=c;++i)    write(vis[i]),putchar(' '),write(i),putchar('\n');
    int up=(1<<k),ans=0;
    for(int s=0;s<up;++s)
    {
        if(fuc[s])    continue;
        bool flag=0,book=0;
        for(int i=1;i<=m;++i)
        {
            if((s>>as[i].w)&1)
            {
                flag=1;
                if(!vis[as[i].s])    book=1;
            }
            if(book)    break;
        }
        if(!flag)    ans++;
        else if(!book)    ans++;
    }
    write(ans);
}
}
int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    solveIt::Main();
    return 0;
}

下来改的：

#include<cstdio>
#include<algorithm>
using namespace std;
namespace solveIt
{
typedef unsigned long long ULL;
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void readull(ULL &x)
{
    x=0;
    char c=getchar();
    ULL f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    write(x/10);
    putchar(x%10+'0');
}
void writeull(ULL x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    writeull(x/10);
    putchar(x%10+'0');
}
const int MAXN=1e6+5;
int n,m,c,k,len;
ULL a[MAXN],all,pri[MAXN];
bool fuc[70],buc[MAXN];
struct ask
{
    int w,s;
    ask(int W=0,int S=0){w=W;s=S;}
}as[MAXN];
void Main()
{
    read(n),read(m),read(c),read(k);
    for(int i=1;i<=n;++i)
    {
        readull(a[i]);
        all|=a[i];
    }
    for(int i=1;i<=m;++i)
    {
        read(as[i].w);
        read(as[i].s);
        pri[i]=as[i].s;
    }
    sort(pri+1,pri+1+m);
    len=unique(pri+1,pri+1+m)-pri-1;
    for(int i=1;i<=m;++i)    as[i].s=lower_bound(pri+1,pri+1+len,as[i].s)-pri;
    for(int i=1;i<=m;++i)
    {
        if((all>>as[i].w)&1)    buc[as[i].s]=1;
    }
    for(int i=1;i<=m;++i)
    {
        if(!buc[as[i].s])    fuc[as[i].w]=1;
    }
    int tot=0;
    for(int i=0;i<k;++i)
    {
        if(!fuc[i])    ++tot;
    }
    if(tot==64)
    {
        if(n==0)    puts("18446744073709551616");
        else
        {
            ULL ans=0,two=1;
            for(int i=1;i<=63;++i)    two<<=1;
            ans+=two;
            ans-=n;
            ans+=two;
            writeull(ans);
        }
    }
    else    writeull((1ull<<tot)-n);
}
}
int main()
{
    // freopen("zoo.in","r",stdin);
    // freopen("zoo.out","w",stdout);
    solveIt::Main();
    return 0;
}

Problem. 3 - Senior Call

这儿

考场代码： （Loneliness）

下来改的：

#include <queue>
#include <cstdio>
#define mod ( 998244353 )

using namespace std;
typedef long long LL;

const int MAXN = 1e6 + 5;

template<typename _T>
void read( _T &x ){
    x = 0; char c = getchar(); _T f = 1;
    while( c < '0' || c > '9' ){ if( c == '-' )    f = -1; c = getchar(); }
    while( c >= '0' && c <= '9' ){ x = ( x << 3 ) + ( x << 1 ) + ( c & 15 ); c = getchar(); }
    x *= f;
}

template<typename _T>
void write( _T x ){
    if( x < 0 ){ putchar( '-' ); x = -x; }
    if( x > 9 )    write( x / 10 );
    putchar( x % 10 + '0' );
}

struct starS{
    int to, nxt;
    starS( int T = 0, int N = 0 ){ to = T; nxt = N; }
} as[MAXN * 2];

struct operateS{
    int Tp, pos;
    LL add, mul, sum;
    operateS( int T = 0, int P = 0, LL A = 0, LL M = 0, LL S = 0 ){ Tp = T; pos = P; add = A; mul = M; sum = S; }
} opS[MAXN];

int N, M, Q;
int totE, totT;
int A[MAXN], topS[MAXN], degS[MAXN], firS[MAXN], queS[MAXN];

void pushEdge( int u, int v ){ as[++ totE] = starS( v, firS[u] ); firS[u] = totE; }

void TopSort( ){
    queue<int> align;
    for( int i = 1; i <= M; ++ i ){
        if( ! degS[i] )    align.push( i );
    }
    while( ! align.empty( ) ){
        int u = align.front( ); align.pop( );
        topS[++ totT] = u;
        for( int i = firS[u]; i; i = as[i].nxt ){
            int v = as[i].to; degS[v] --;
            if( ! degS[v] ) align.push( v );
        }
    }
}

int main( ){
    read( N );
    for( int i = 1; i <= N; ++ i )  read( A[i] );
    read( M );
    for( int i = 1; i <= M; ++ i ){
        read( opS[i].Tp );
        if( opS[i].Tp == 1 ){
            read( opS[i].pos ); read( opS[i].add );
            opS[i].mul = 1;
        }
        else if( opS[i].Tp == 2 ) {
            read( opS[i].mul );
            opS[i].add = opS[i].mul;
        }
        else{
            read( opS[i].pos );
            opS[i].mul = 1;
            for( int j = 1, to; j <= opS[i].pos; ++ j ){ read( to ); pushEdge( i, to ); degS[to] ++; }
        }
    }
    TopSort( );
    for( int i = M; i; -- i ){
        int u = topS[i];
        for( int j = firS[u]; j; j = as[j].nxt ){
            int v = as[j].to;
            opS[u].mul = ( LL )opS[u].mul * opS[v].mul % mod;
        }
    }
    read( Q ); int now = 1;
    for( int i = 1; i <= Q; ++ i )  read( queS[i] );
    for( int i = Q; i; -- i ){ opS[queS[i]].sum = ( ( LL )opS[queS[i]].sum + now ) % mod; now = ( LL )now * opS[queS[i]].mul % mod; }
    for( int i = 1; i <= M; ++ i ){
        int u = topS[i], now = 1;
        for( int j = firS[u]; j; j = as[j].nxt ){
            int v = as[j].to;
            opS[v].sum = ( ( LL )opS[u].sum * now % mod + opS[v].sum ) % mod;
            now = ( LL )now * opS[v].mul % mod;
        }
    }
    for( int i = 1; i <= N; ++ i )  A[i] = ( LL )A[i] * now % mod;
        for( int i = 1; i <= M; ++ i ){
        if( opS[i].Tp == 1 )    A[opS[i].pos] = ( A[opS[i].pos] + ( LL )opS[i].add * opS[i].sum % mod ) % mod;
    }
    for( int i = 1; i <= N; ++ i )  write( A[i] ), putchar( ' ' );
    return 0;
}

Problem. 4 - Senior Snakes

先讲个 $\texttt{70pts}$ 的做法。没脑子吃，然后回来判断。所有大样例有些多一的代码改一下就有。

正解应该就是利用序列单调性把 $\texttt{70pts}$ 的暴力的线段树改成其他的东西。

目前还没做出来，可以欣赏一下我考场的 186 行 SGST（含义见代码）。

考场代码：

（upd：这份代码下面是 $\texttt{70pts}$ 的代码：）

#include<cstdio>
#include<algorithm>
using namespace std;
namespace solveIt
{
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')    f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)    write(x/10);
    putchar(x%10+'0');
}
struct node
{
    int val,pos;
    node(int V=0,int P=0)
    {
        val=V;
        pos=P;
    }
    bool operator<(const node&ano)const
    {
        if(val==ano.val)    return pos<ano.pos;
        else    return val<ano.val;
    }
};
const int MAXN=1e6+6;
int n,a[MAXN];
struct TREE
{
node mnx[MAXN*4],mxx[MAXN*4];
void upd(int x)
{
    mnx[x]=min(mnx[x<<1],mnx[x<<1|1]);
    mxx[x]=max(mxx[x<<1],mxx[x<<1|1]);
}
void build(int x,int l,int r)
{
    if(l^r)
    {
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        upd(x);
    }
    else
    {
        mnx[x]=node(a[l],l);
        mxx[x]=node(a[l],l);
    }
}
void ins(int x,int l,int r,int pos,int val)
{
    if(l^r)
    {
        int mid=(l+r)>>1;
        if(mid>=pos)    ins(x<<1,l,mid,pos,val);
        else    ins(x<<1|1,mid+1,r,pos,val);
        upd(x);
    }
    else
    {
        mnx[x].val+=val;
        mxx[x].val+=val;
    }
}
node findmin(int x,int l,int r,int fr,int ba)
{
    if(l>ba||r<fr)    return 1e9;
    if(l>=fr&&r<=ba)    return mnx[x];
    else
    {
        int mid=(l+r)>>1;
        return min(findmin(x<<1,l,mid,fr,ba),findmin(x<<1|1,mid+1,r,fr,ba));
    }
}
node findmax(int x,int l,int r,int fr,int ba)
{
    if(l>ba||r<fr)    return 0;
    if(l>=fr&&r<=ba)    return mxx[x];
    else
    {
        int mid=(l+r)>>1;
        return max(findmax(x<<1,l,mid,fr,ba),findmax(x<<1|1,mid+1,r,fr,ba));
    }
}
} tmx,tmn;
void Main()
{
    int t;
    read(t);
    int flag=1;
    while(t--)
    {
        read(n);
        if(flag==1)
        {
            for(int i=1;i<=n;++i)    read(a[i]);
            flag=0;
        }
        else
        {
            for(int i=1,p,v;i<=n;++i)
            {
                read(p);
                read(v);
                int tmxv=tmx.findmax(1,1,n,p,p).val;
                int tmnv=tmn.findmin(1,1,n,p,p).val;
                tmx.ins(1,1,n,p,-tmxv);
                tmx.ins(1,1,n,p,v);
                tmn.ins(1,1,n,p,-tmnv);
                tmn.ins(1,1,n,p,v);
            }
            for(int i=1;i<=n;++i)    a[i]=tmx.findmax(1,1,n,i,i).val;
//            for(int i=1;i<=n;++i)    write(a[i]),putchar(' '); puts("");
        }
        tmx.build(1,1,n);
        tmn.build(1,1,n);
        int ans=n;
        while(true)
        {
            node nowmax=tmx.findmax(1,1,n,1,n);
            tmx.ins(1,1,n,nowmax.pos,-nowmax.val);
            node secmax=tmx.findmax(1,1,n,1,n);
            tmx.ins(1,1,n,nowmax.pos,nowmax.val);
            
            node nowmin=tmn.findmin(1,1,n,1,n);
            tmn.ins(1,1,n,nowmin.pos,-nowmin.val+1e9);
            node secmin=tmn.findmin(1,1,n,1,n);
            tmn.ins(1,1,n,nowmin.pos,nowmin.val-1e9);
//            printf("nmx=(%d %d),nmn=(%d %d),smx=(%d %d),smn(%d %d)\n",nowmax.pos,nowmax.val,
//                nowmin.pos,nowmin.val,secmax.pos,secmax.val,secmin.pos,secmin.val);
            if(((nowmax.val-nowmin.val<secmin.val)
                &&((nowmax.val-nowmin.val>secmax.val)
                    ||(nowmax.val-nowmin.val==secmax.val&&nowmax.pos>secmax.pos)))
                ||(((nowmax.val-nowmin.val==secmin.val)&&(nowmax.pos<secmin.val))
                    &&((nowmax.val-nowmin.val>secmax.val)
                        ||((nowmax.val-nowmin.val==secmax.val)&&(nowmax.pos>secmax.pos))))
                ||(nowmax.val-nowmin.val>secmin.val)
                ||((nowmax.val-nowmin.val==secmin.val)&&(nowmax.pos>secmin.pos)))
            {
                tmn.ins(1,1,n,nowmax.pos,-nowmin.val);
                tmn.ins(1,1,n,nowmin.pos,-nowmin.val+1e9);
                tmx.ins(1,1,n,nowmax.pos,-nowmin.val);
                tmx.ins(1,1,n,nowmin.pos,-nowmin.val);
                ans--;
            }
            else    break;
        }
        write(ans);
        putchar('\n');
    }
}
}
int main()
{
//    freopen("D:/csp-s(windows)/snakes/snakes3.in","r",stdin);
    freopen("snakes.in","r",stdin);
    freopen("snakes.out","w",stdout);
    solveIt::Main();
    return 0;
}
/*
SGST - Strong-Guy Segment Tree
*/

$\texttt{70pts}$

#include<cstdio>
#include<algorithm>
using namespace std;
namespace solveIt
{
void read(int &x)
{
    x=0;
    char c=getchar();
    int f=1;
    while(c<'0'||c>'9')
    {
        if(c=='-')  f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^'0');
        c=getchar();
    }
    x*=f;
}
void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
struct node
{
    int val,pos;
    node(int V=0,int P=0)
    {
        val=V;
        pos=P;
    }
    bool operator<(const node&ano)const
    {
        if(val==ano.val)    return pos<ano.pos;
        else    return val<ano.val;
    }
};
const int MAXN=1e6+6;
int n,ans,a[MAXN];
struct TREE
{
node mnx[MAXN*4],mxx[MAXN*4];
int siz,tp;
TREE()
{
    siz=0;
}
void upd(int x)
{
    mnx[x]=min(mnx[x<<1],mnx[x<<1|1]);
    mxx[x]=max(mxx[x<<1],mxx[x<<1|1]);
}
void build(int x,int l,int r)
{
    if(l^r)
    {
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid+1,r);
        upd(x);
    }
    else
    {
        mnx[x]=node(a[l],l);
        mxx[x]=node(a[l],l);
    }
}
void ins(int x,int l,int r,int pos,int val)
{
    if(l^r)
    {
        int mid=(l+r)>>1;
        if(mid>=pos)    ins(x<<1,l,mid,pos,val);
        else    ins(x<<1|1,mid+1,r,pos,val);
        upd(x);
    }
    else
    {
        mnx[x].val+=val;
        mxx[x].val+=val;
    }
}
node findmin(int x,int l,int r,int fr,int ba)
{
    if(l>ba||r<fr)  return 1e9;
    if(l>=fr&&r<=ba)    return mnx[x];
    else
    {
        int mid=(l+r)>>1;
        return min(findmin(x<<1,l,mid,fr,ba),findmin(x<<1|1,mid+1,r,fr,ba));
    }
}
node findmax(int x,int l,int r,int fr,int ba)
{
    if(l>ba||r<fr)  return 0;
    if(l>=fr&&r<=ba)    return mxx[x];
    else
    {
        int mid=(l+r)>>1;
        return max(findmax(x<<1,l,mid,fr,ba),findmax(x<<1|1,mid+1,r,fr,ba));
    }
}
void del(node one)
{
    if(tp==1)    ins(1,1,n,one.pos,-one.val);
    else    ins(1,1,n,one.pos,-one.val+1e9);
    siz--;
}
void buildemp(int f,int n)
{
    build(1,1,n);
    siz=n;
    tp=f;
}
};
struct treetoheap
{
TREE tmx,tmn;
node findmax(int l,int r)
{
    return tmx.findmax(1,1,n,l,r);
}
node findmin(int l,int r)
{
    return tmn.findmin(1,1,n,l,r);
}
void ins(node one)
{
    tmx.siz++;
    tmn.siz++;
    tmx.ins(1,1,n,one.pos,one.val);
    if(tmn.findmin(1,1,n,one.pos,one.pos).val==(int)1e9)    tmn.ins(1,1,n,one.pos,one.val-1e9);
    else    tmn.ins(1,1,n,one.pos,one.val);
}
void del(node one)
{
    tmx.del(one);
    tmn.del(one);
}
void buildemp(int n)
{
    tmx.buildemp(1,n);
    tmn.buildemp(0,n);
}
int siz()
{
    return tmx.siz;
}
} wer;
bool dfs()
{
    if(wer.siz()==2)    return 1;
    int f=0;
    while(wer.siz()>=3)
    {
        int siz=wer.siz();
        node nowmin=wer.findmin(1,n),nowmax=wer.findmax(1,n);
        wer.del(nowmin);
        wer.del(nowmax);
        node secmin=wer.findmin(1,n);
        wer.ins(node(nowmax.val-nowmin.val,nowmax.pos));
//        puts("\n/********************************************/");
//        printf("(%d %d %d)\n",secmin.val,secmin.pos,wer.siz());
//        for(int i=1;i<=n;++i)    printf("%d ",wer.findmax(i,i).val);puts("");
//        puts("/********************************************/\n");
        if(nowmax.val-nowmin.val<secmin.val)
        {
            if(!dfs())
            {
                ans=siz-1;
                return 1;
            }
            else if(f)
            {
                ans=siz;
                return 1;
            }
            else
            {
                ans=siz;
                return 0;
            }
        }
        ++f;
    }
    ans=1;
    return 1;
}
void Main()
{
    int t;
    read(t);
    int flag=1;
    while(t--)
    {
        if(flag==1)
        {
            read(n);
            for(int i=1;i<=n;++i)   read(a[i]);
            flag=0;
        }
        else
        {
            int tmp;
            read(tmp);
            for(int i=1,p,v;i<=tmp;++i)
            {
                read(p);
                read(v);
                a[p]=v;
            }
        }
        if(n==3)
        {
            if(a[1]+a[2]<=a[3])    puts("1");
            else    puts("3");
            continue;
        }
        wer.buildemp(n);
        ans=n;
        bool WASTED=dfs();
        write(ans);
        putchar('\n');
        WASTED=!WASTED;
    }
}
}
int main()
{
//    freopen("snakes/snakes4.in","r",stdin);
//    freopen("snakes/fuck.out","w",stdout);
//    freopen("snakes.in","r",stdin);
//    freopen("snakes.out","w",stdout);
    solveIt::Main();
    return 0;
}
/*
SGST - Strong-Guy Segment Tree
*/