\(CHNUM\)

显然正数一组，负数一组

for(int T=read();T;--T){    n=read(),c=d=0;    fp(i,1,n)x=read(),x>0?++c:++d;    if(!c)c=d;if(!d)d=c;    if(c

\(CHDIGER\)

从原来的数列中选出字典序最小的上升子序列，往后面加\(d\)就行了

//minamoto#include
    
     #define R register#define ll long long#define inline __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char s[25];int t[25],d,top,n,pos,mn;int main(){//  freopen("testdata.in","r",stdin);    int T;scanf("%d",&T);    while(T--){        scanf("%s%d",s+1,&d),top=0,n=strlen(s+1);        pos=1;        while(pos<=n){            mn=10;            fp(i,pos,n)if(s[i]-'0'
      
       d)--top;        while(top
      
     
    

\(JAIN\)

压成一个\(5\)位的二进制数，高位前缀和然后乱搞就可以了

//minamoto#include
    
     #define R register#define ll long long#define inline __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}int read(char *s){    R int len=0;R char ch;while(((ch=getc())>'z'||ch<'a'));    for(s[++len]=ch;(ch=getc())>='a'&&ch<='z';s[++len]=ch);    return s[len+1]='\0',len;}const int N=1e5+5;char s[1005];int n,m,v,sum[35],p[35];ll res;int main(){//  freopen("testdata.in","r",stdin);    for(int T=read();T;--T){        n=read(),res=0;        fp(i,0,31)sum[i]=p[i]=0;        fp(i,1,n){            m=read(s),v=0;            fp(j,1,m){                v|=(s[j]=='a'),                v|=(s[j]=='e')<<1,                v|=(s[j]=='i')<<2,                v|=(s[j]=='o')<<3,                v|=(s[j]=='u')<<4;            }            ++sum[v];        }        fp(i,0,31)p[i]=sum[i];        fp(j,0,4)fp(i,0,31)if(i>>j&1)p[i^(1<
      
       >1);    }    return 0;}
      
     
    

\(SUBPRNJL\)

显然有\(m=\left\lceil{k\over r-l+1}\right\rceil\)，以及选中的数字是\([l,r]\)中\(sort\)之后的第\(\left\lceil{k\over m}\right\rceil\)个数。区间第\(k\)小可以记录一下前缀和之后二分

//minamoto#include
    
     #define R register#define inline __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=2005;int sz[N][N],sum[N][N],n,k,x,m,res;int find(int bl,int br,int k){    int l=1,r=2000,ans=0,mid;    while(l<=r){        mid=(l+r)>>1;        sum[br][mid]-sum[bl-1][mid]>=k?(ans=mid,r=mid-1):l=mid+1;    }    return ans;}int main(){//  freopen("testdata.in","r",stdin);    for(int T=read();T;--T){        n=read(),k=read(),res=0;        fp(i,1,n){            memset(sum[i],0,(n+1)<<2);            memset(sz[i],0,(n+1)<<2);            x=read(),sz[i][x]=1;            fp(j,1,2000)sz[i][j]+=sz[i-1][j];            fp(j,1,2000)sum[i][j]=sum[i][j-1]+sz[i][j];        }        fp(l,1,n)fp(r,l,n){            m=(k+r-l)/(r-l+1),x=(k+m-1)/m;            x=find(l,r,x),x=sz[r][x]-sz[l-1][x];            if(sz[r][x]-sz[l-1][x])++res;        }        printf("%d\n",res);    }    return 0;}
     
    

\(CHONQ\)

因为形如\(\left\lfloor{n\over i}\right\rfloor\)的取值只有\(O(\sqrt{n})\)种，我们可以直接整除分块来预处理一下贡献

然而不知道为何我的整除分块\(T\)掉了……我的暴力交上去却\(A\)了……

还是换种写法吧，我们把\(i\)左边前\(\sqrt{a_i}\)个数暴力加上贡献，后面的用类似前缀和的办法在分界点预处理贡献。最后把前缀和加起来就好了

//minamoto#include
    
     #define R register#define inline __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=1e5+5;int a[N],d[N][317],c[N],lst[N],n,k,res,pos;int main(){//  freopen("testdata.in","r",stdin);    fp(i,1,100000)fp(j,1,sqrt(i))d[i][j]=i/j;    fp(i,1,100000)lst[i]=sqrt(i);    for(int T=read();T;--T){        n=read(),k=read();        fp(i,1,n)a[i]=read(),c[i]=0;        fp(i,1,n){            for(R int j=1,pos;j<=lst[a[i]];++j){                pos=max(1,i-d[a[i]][j]+1);                c[pos]-=j-1,c[pos]+=j;            }            int j=lst[a[i]],pos=max(1,i-j+1);            c[pos]-=j,c[pos]+=d[a[i]][j];            for(R int j=lst[a[i]]-1,pos;j;--j){                pos=max(1,i-j+1);                c[pos]-=d[a[i]][j+1],c[pos]+=d[a[i]][j];            }            c[i+1]-=a[i];        }        res=0,pos=n+1;        fp(i,1,n){            res+=c[i];            if(res<=k){pos=i;break;}        }        printf("%d\n",pos);    }    return 0;}
     
    

\(CHEFSOC\)

我永远讨厌\(dp.jpg\)

我们设\(f_{i,0/1}\)表示从前面跳过来，\(0/1\)表示\(i-1\)是否被跳到过，的方案数，转移的话可以看代码，比较显然

然后还有一个问题是它可能从后面跳过来……这种情况肯定是先跳到\(i+1\)，然后在后面经历了一番不可描述的事情之后跳回了\(i\)。我们设\(g_i\)表示从\(i+1\)跳回到\(i\)的方案，这个转移也看代码好了……

//minamoto#include
    
     #define R register#define inline __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=1e5+5,P=1e9+7;inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int f[N][2],g[N],a[N],res,n;int main(){//  freopen("testdata.in","r",stdin);    for(int T=read();T;--T){        n=read(),res=0;        fp(i,1,n)a[i]=read();        f[1][0]=1,f[1][1]=0;        fp(i,2,n){            f[i][1]=add(f[i-1][0],f[i-1][1]),f[i][0]=0;            if(a[i-2]==2)f[i][0]=add(f[i-2][0],f[i-2][1]),upd(f[i][1],f[i-1][0]);        }        g[n]=g[n+1]=0,res=add(f[n][0],f[n][1]);        fd(i,n-1,1){            upd(res,add(f[i][0],f[i][1])),g[i]=1;            if(a[i+1]==2&&a[i+2]==2)upd(g[i],g[i+2]);            if(a[i+2]==2)++g[i];            upd(res,mul(f[i+1][0],g[i]));        }        printf("%d\n",res);    }    return 0;}
     
    

\(PTREE\)

没有题解的代码食用体验极差……

用了一个晚上看懂代码，又用了一个早上调自己的代码……

因为本题非常需要卡常，所以您最好先知道一些卡常用的小\(trick\)

\(O(1)\)快速幂

简单来说我们需要在给定\(x\)的情况下多次求\(x^i\)

我们可以令\(s=\sqrt{P}\)，预处理出\(x^0,x^1,...,x^s\)，以及\(x^0,x^s,x^{2s},...\)，然后就可以\(O(1)\)查询了

不过本题中最大只需要查到\(x^n\)，所以这里我们令\(s=\sqrt{n}\)就可以了

等比数列求和

如果要计算形如\(\sum\limits_{i=0}^{k-1}p^i\)，可以直接用等比数列求和公式代入计算\({1-p^k\over1-p}\)，复杂度\(O(\log P)\)（求逆元）

或者把长为\(k\)的数列拆成\(\log k\)段计算，复杂度\(O(\log k)\)

int calc(R int x,R int y){    R int res=1,d=1;    for(--y;y;y>>=1,d=add(mul(d,x),d),x=mul(x,x))(y&1)?res=add(mul(res,x),d):0;    return res;}

题解

因为这是一个完美树，所以显然深度为\(k\)的点数大于等于深度为\(k-1\)的点数

我们定义一个深度\(k\)为特殊的，当且仅当深度为\(k\)的点数大于深度为\(k-1\)的点数。不难发现特殊深度的个数是\(O(\sqrt{n})\)的

对于任何一棵子树来说，第\(i\)个特殊深度和第\(i-1\)个特殊深度之间所有深度的点数都相同

我们找出所有的特殊深度，并将它们的值离散化，然后再做一个前缀和，令\(sm[i][j]\)表示\(1\)到\(i\)之间深度为\(j\)的点数有多少个（这里的深度是离散化之后的特殊深度），\(i\)表示的是\(dfs\)序。那么我们就可以用前缀和相减的形式来求出一棵子树内某个特定深度的点数了

然后我们再设一个\(nxt[k]\)，表示\(k\)之后的下一个特殊深度是什么（这里的深度是没有离散化过的）。对于询问\((u,x)\)，我们从\(dep[u]\)开始不断跳\(nxt\)，根据性质跳的次数是\(O(\sqrt{n})\)的

那么设当前子树内\([l,r-1]\)之间的所有深度的点数都相同，设为\(k\)，且深度为\([dep[u],l-1]\)之间的点数共有\(s\)个，令\(d=dep[u]\)，我们需要快速处理贡献

很容易写出一个暴力，贡献即为

\[Ans=\sum_{i=l}^{r-1}x^{sum+(i-l)k}(i-d)\sum_{j=0}^{k-1}x^j\]

如果直接暴力处理贡献的话，虽然后面等比数列求和可以用之前说的\(O(\log k)\)搞，但是前面显然是\(O(n)\)的……肯定\(gg\)啊……

鉴于代码里原本写的东西我实在看不太懂，所以换了一种方式

那就开始推倒吧

\[ \begin{aligned} Ans &=\sum_{i=l}^{r-1}x^{sum+(i-l)k}(i-d)\sum_{j=0}^{k-1}x^j\\ &=\sum_{i=l}^{r-1}x^{sum+(i-l)k}(i-d){x^k-1\over x-1}\\ &={x^{sum}\over x-1}\sum_{i=l}^{r-1}x^{(i-l)k}(i-d)(x^k-1) \end{aligned} \]

令\(p=x^k\)，并忽略\(\sum\)前面的那些常数

\[ \begin{aligned} Ans &=\sum_{i=l}^{r-1}p^{i-l}(i-d)(p-1)\\ &=\sum_{i=l}^{r-1}p^{i-l}i(p-1)-\sum_{i=l}^{r-1}p^{i-l}d(p-1) \end{aligned} \]

对于后面，可以化成

\[ \begin{aligned} \sum_{i=l}^{r-1}p^{i-l}d(p-1) &=d(p-1)\sum_{i=0}^{r-l-1}p^i\\ \end{aligned} \]

后面就是个等比数列求和的形式，按上面说的搞就行了

对于前面，有

\[ \begin{aligned} \sum_{i=l}^{r-1}p^{i-l}i(p-1) &=(p-1)\sum_{i=0}^{r-l-1}p^i(i+l)\\ &=(p-1)\sum_{i=0}^{r-l-1}p^ii+(p-1)l\sum_{i=0}^{r-l-1}p^i \end{aligned} \]

后面还是个等比数列求和的形式，关键是前面

简单来说，我们需要对一个形如

\[\sum_{i=0}^{n-1}p^i\times i\]

的东西求和

这就是个等比\(+\)等差数列的求和，根据高中数学必修五的芝士，可得它等于

\[{p^n(n-1)-\sum_{i=1}^{n-1}p^i\over p-1}\]

分母里，前面的快速幂我们已经预处理过了，后面又是个等比数列求和，老办法搞

然后没有然后了，细节可以看代码

一道树据结构题被我硬生生做成了数学题

//minamoto#include
    
     #define R register#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmax(T&a,const T&b){return a
       
        '9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R int x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}const int N=5e5+5,L=455,P=1e9+7;inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;    return res;}int gsum(R int x,R int y){    if(!y)return 0;    R int res=1,d=1;    for(--y;y;y>>=1,d=add(mul(d,x),d),x=mul(x,x))(y&1)?res=add(mul(res,x),d):0;    return res;}struct eg{int v,nx;}e[N<<1];int head[N],tot;inline void Add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}int sz[N],dfn[N],rs[N],sm[N][1005],bin[L+5],bp[L+5],id[N],nxt[N],dep[N],sum[N];int fi[N],se[N];int n,m,cnt,t,D,lasans;void dfs(int u,int fa){    ++sz[dep[u]=dep[fa]+1],dfn[u]=++cnt,sum[u]=dep[u];    go(u)if(v!=fa)dfs(v,u),sum[u]=add(sum[u],sum[v]);    rs[u]=cnt;}void clr(){    memset(head,0,(n+1)<<2);    memset(sz,0,(n+1)<<2);    fp(i,1,n)memset(sm[i],0,(t+1)<<2);}int main(){//  freopen("testdata.in","r",stdin);    fp(i,1,N-1)fi[i]=i/L,se[i]=i%L;    for(int T=read();T;--T){        n=read(),m=read(),tot=0;        for(R int i=1,u,v;i
       
      
     
    

\(MATPER\)

我讨厌搜索\(.jpg\)

我们先对每一个\(P_i\)都跑一遍\(kmp\)，找出它在\(s\)中出现的所有位置，并预处理出\(f_{i,k}\)表示位置\(k\)之后第一个\(P_i\)结尾的位置，以及\(g_{i,k}\)表示位置\(k\)之前第一个\(P_i\)结尾的位置

然后我们\(meet-in-the-middle\)就行了

//minamoto#include
    
     #define R register#define pb push_back#define ll long long#define IT vector
     
      ::iterator#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
      
       I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}int read(char *s){    R int len=0;R char ch;while(((ch=getc())>'z'||ch<'a'));    for(s[++len]=ch;(ch=getc())>='a'&&ch<='z';s[++len]=ch);    return s[len+1]='\0',len;}const int N=1e5+5,M=15;char s[N],p[M][N];int lp[M],f[M][N],g[M][N],lg[(1<
       
        <
        
         
          c[N],cc[N],pos[M];int n,m,u,t;ll res;void dfs1(int st,int ch,int ed){ if(st==t)return c[ed].pb(ch),void(); int y; for(int x=u^ch,i=lg[x&-x]+1;x;x&=x-1,i=lg[x&-x]+1) if(!pos[i].empty()&&pos[i].back()-lp[i]+1>ed){ y=f[i][ed+lp[i]]; if(~y)dfs1(st+1,ch|(1<<(i-1)),y); }}void dfs2(int st,int ch,int op){ if(st==t+1)return cc[op].push_back(ch),void(); int y; for(int x=u^ch,i=lg[x&-x]+1;x;x&=x-1,i=lg[x&-x]+1) if(!pos[i].empty()&&pos[i].front()
          
           >1; dfs1(0,0,0),dfs2(m+1,0,n+1); fd(i,n+1,0){ fp(j,0,c[i].size()-1)res+=sz[u^c[i][j]]; fp(j,0,cc[i].size()-1)++sz[cc[i][j]]; } printf("%lld\n",res); return 0;}
          
         
        
       
      
     
    

\(TREASURE\)

把它写成若干个异或方程组，解的个数就是\(2^{自由元个数}\)

//minamoto#include
    
     #define R register#define inline __inline__ __attribute__((always_inline))#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;const int N=905,P=1e9+7;inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;    return res;}bitset
      
       a[N];int n,m;inline int id(R int i,R int j){return (i-1)*m+j;}int Gauss(int n,int m){    int res=m-1;    fp(i,0,n-1){        int x=a[i]._Find_first();        if(x==m)return -1;        if(x>m)continue;        --res;        fp(j,i+1,n-1)if(a[j][x])a[j]^=a[i];    }    return res;}int main(){//  freopen("testdata.in","r",stdin);    int T;scanf("%d",&T);    while(T--){        scanf("%d%d",&n,&m);        int tot=0,mx=n*m+1,x;        fp(i,1,n)fp(j,1,m){            scanf("%d",&x);            if(x==-1)continue;            a[tot]=0;            if(i>1)a[tot][id(i-1,j)]=1;            if(j>1)a[tot][id(i,j-1)]=1;            if(i
      
     
    

\(SONATR\)

代码两百多行的……咕咕……