A. As Easy As Possible

每个点往右贪心找最近的点，可以得到一棵树，然后倍增查询即可。

时间复杂度$O((n+m)\log n)$。

#include 
     
      using namespace std ;typedef long long LL ;typedef long long Int ;typedef pair < int , int > pi ;#define clr(a,x) memset ( a , x , sizeof a ) char s[100020];int a[100020];int n;int nxt[100020][4];int dp[18][100020];int cg(char c){	if(c=='e')return 0;	if(c=='a')return 1;	if(c=='s')return 2;	return 3;}void prepare(){	int cur[4];	for(int i=0;i
      
       =0;i--){		cur[a[i]]=i;		for(int j=0;j<4;j++){			nxt[i][j]=cur[j];		}	}	for(int i=0;i<4;i++)nxt[n][i]=n;	for(int i=0;i
       
        =n){dp[it][i]=n;continue;}			dp[it][i]=dp[it-1][to];		}	}	/*	for(int i=0;(1<
        
         <=n;i++){		for(int j=0;j
         
          =0&&l<=r;i--){			if(dp[i][l]<=r){			//	printf("l=%d dp=%d\n",l,dp[i][l]);				ans|=1<
         
        
       
      
     

　　

B. Be Friends

从高位到低位依次考虑，对于每一位，按这一位将数字分成两个集合，显然这两个集合要优先连边，那么只需要找到横跨这两个集合的最小的边即可，用Trie完成查询。

时间复杂度$O(n\log^2m)$。

#include
     
      #include
      
       const int N=100010,M=N*32;int n,i,a[N],q[N],son[M][2],tot;long long ans;inline void ins(int p){  for(int o=29,x=0;~o;o--){    int w=p>>o&1;    if(!son[x][w])son[x][w]=++tot;    x=son[x][w];  }}inline int ask(int p){  int t=0;  for(int o=29,x=0;~o;o--){    int w=p>>o&1;    if(son[x][w])x=son[x][w];else x=son[x][w^1],t|=1<
       
        r)return;  int L=l-1,R=r+1;  for(int i=l;i<=r;i++)if(a[i]>>o&1)q[++L]=a[i];else q[--R]=a[i];  for(int i=l;i<=r;i++)a[i]=q[i];  solve(o-1,l,L),solve(o-1,R,r);  if(l>L||R>r)return;  for(int i=l;i<=L;i++)ins(a[i]);  int ret=~0U>>1;  for(int i=R;i<=r;i++)ret=std::min(ret,ask(a[i]));  ans+=ret;  for(int i=0;i<=tot;i++)son[i][0]=son[i][1]=0;  tot=0;}int main(){  scanf("%d",&n);  for(i=1;i<=n;i++)scanf("%d",&a[i]);  solve(29,1,n);  printf("%lld",ans);  return 0;}
       
      
     

　　

C. Coprime Heaven

留坑。

 

D. Drawing Hell

游戏的最终局面一定是一个三角剖分，因此边数只与凸包上的点数有关，判一下奇偶性即可。

 

E. Easiest Game

合法的$(r,s)$需要满足：

1.$r+s\leq\min(n,m)$

2.$\gcd(r,s)=1$

3.$r\bmod 2\neq s\bmod 2$

4.$\max(r,s)\leq\lfloor\frac{\max(n,m)}{2}\rfloor$

假设没有互质的限制，那么可以直接$O(1)$算出答案$f(n,m)$，加上限制之后$ans=\sum_{d}\mu(d)f(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)$，分段计算即可。

时间复杂度$O(n+T\sqrt{n})$。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
           
          
         
        
       
      
     

　　

F. Fibonacci of Fibonacci

打表可以发现循环节为$26880696$，然后直接用矩阵快速幂计算答案即可。

#include
     
      #define rep(i) for(int i=0;i<2;i++)int T,n,P;struct mat{  int v[2][2];  mat(){rep(i)rep(j)v[i][j]=0;}  mat operator*(const mat&b){    mat c;    rep(i)rep(j)rep(k)c.v[i][j]=(1LL*v[i][k]*b.v[k][j]+c.v[i][j])%P;    return c;  }}G,B;int fib(int n,int p){  P=p;  G=B=mat();  G.v[0][1]=G.v[1][0]=G.v[1][1]=B.v[1][0]=1;  for(;n;n>>=1,G=G*G)if(n&1)B=G*B;  return B.v[0][0];}int main(){  scanf("%d",&T);  while(T--)scanf("%d",&n),printf("%d\n",fib(fib(n,26880696),20160519));  return 0;}
     

　　

G. Global Warming

留坑。

 

H. Hash Collision

设$f[i][j]$表示长度为$i$的串中Hash值为$j$的方案数，那么$ans=\sum_{i=0}^{m-1}C(f[n][i],2)$。

从$f[i][]$转移到$f[i+1][]$的复杂度为$O(26)$，而从$f[i][]$转移到$f[2i][]$可以用FFT做到$O(m\log m)$，因此倍增计算$f[n][]$即可。

时间复杂度$O(m\log m\log n)$。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=65555,P=1000003,M=1000;int n,i,j,k,pos[N],f[N],g[N],seed,m,ans;int A[N],B[N],C[N];namespace FFT{struct comp{	double r,i;comp( double _r=0, double _i=0){r=_r,i=_i;}	comp operator+(const comp&x){return comp(r+x.r,i+x.i);}	comp operator-(const comp&x){return comp(r-x.r,i-x.i);}	comp operator*(const comp&x){return comp(r*x.r-i*x.i,r*x.i+i*x.r);}	comp conj(){return comp(r,-i);}}A[N],B[N];int a0[N],b0[N],a1[N],b1[N];const double pi=acos(-1.0);void FFT(comp*a,int n,int t){	for(int i=1;i
        
         
          >1]>>1|((i&1)<
          
           >=1; for(j='A';j<='Z';j++)f[j%m]++; for(int o=cnt-1;o;o--){ for(i=0;i
          
         
        
       
      
     

　　

I. Increasing or Decreasing

经典数位DP。

#include 
     
      using namespace std ;typedef long long LL ;typedef pair < int , int > pi ;#define clr(a,x) memset ( a , x , sizeof a ) typedef long long Int ;int dp[20][3][10][2];int num[22];int dfs(int cur,int dd,int bef,int qd){	if(cur<0)return 1;	int &t=dp[cur][dd][bef][qd];	if(t>=0)return t;	t=0;	for(int i=0;i<10;i++){		if((dd==1)&&(i>bef)&&qd)continue;		if((dd==2)&&(i
      
       0);		if(qd==0)ndd=0;		else{			if(i
       
        bef)ndd=2;			else ndd=dd;		}		t+=dfs(cur-1,ndd,i,nqd);	}	return t;}int deal(LL x){	if(!x)return 1;	int tot=0;	while(x){num[tot++]=x%10,x/=10;}	reverse(num,num+tot);	int dd=0;	int ret=0;	for(int i=0;i
        
         num[i-1])curdd=2;				else if(j==num[i-1])curdd=0;				else curdd=1;			}			if(dd&&curdd&&(dd!=curdd))continue;			int nqd=((i==0)&&(j==0))?0:1;			ret+=dfs(tot-i-2,max(dd,curdd),j,nqd);			//if(!i)printf("val=%d\n",tot-i-2);		}		if(i==0)curdd=0;		else{			if(num[i]>num[i-1])curdd=2;			else if(num[i]==num[i-1])curdd=0;			else curdd=1;		}		//printf("%d %d ret=%d\n",i,num[i],ret);		if(dd&&curdd&&(dd!=curdd)){dd=-1;break;}		//printf("dd=%d curdd=%d\n",dd,curdd);		dd=max(dd,curdd);	}	if(dd>=0)ret++;	return ret;}int main(){	memset(dp,-1,sizeof dp);	int _;scanf("%d",&_);	while(_--){		LL l,r;		scanf("%lld%lld",&l,&r);		int ans=deal(r);		ans-=deal(l-1);		printf("%d\n",ans);	}	return 0;}
        
       
      
     

　　

J. Just Convolution

因为数据随机，所以可以取出$A$中最大$200$项和$B$中所有项暴力更新答案，然后再取出$B$中最大$200$项和$A$中所有项暴力更新答案，最后再取出$A$中和$B$中最大的$3000$项更新答案即可。

#include 
     
      using namespace std ;const int MAXN = 200005 ;struct Node {	int x , i ;	bool operator < ( const Node& a ) const {		return x > a.x ;	}} ;Node a[MAXN] , b[MAXN] ;int c[MAXN] ;int n ;void solve () {	for ( int i = 0 ; i < n ; ++ i ) {		scanf ( "%d" , &a[i].x ) ;		a[i].i = i ;	}	for ( int i = 0 ; i < n ; ++ i ) {		scanf ( "%d" , &b[i].x ) ;		b[i].i = i ;	}	for ( int i = 0 ; i < n ; ++ i ) {		c[i] = 0 ;	}	sort ( a , a + n ) ;	sort ( b , b + n ) ;	int k = min ( n , 3000 ) ;	for ( int i = 0 ; i < k ; ++ i ) {		for ( int j = 0 ; j < k ; ++ j ) {			int t = ( a[i].i + b[j].i ) % n ;			c[t] = max ( c[t] , a[i].x + b[j].x ) ;		}	}	int m = min ( n , 200 ) ;	for ( int i = k ; i < n ; ++ i ) {		for ( int j = 0 ; j < m ; ++ j ) {			int t1 = ( a[i].i + b[j].i ) % n ;			int t2 = ( b[i].i + a[j].i ) % n ;			c[t1] = max ( c[t1] , a[i].x + b[j].x ) ;			c[t2] = max ( c[t2] , b[i].x + a[j].x ) ;		}	}	for ( int i = 0 ; i < n ; ++ i ) {		i && putchar ( ' ' ) ;		printf ( "%d" , c[i] ) ;	}	puts ( "" ) ;}int main () {	while ( ~scanf ( "%d" , &n ) ) solve () ;	return 0 ;}