A. Accommodation Plan

对于已知的$K$个点，离它们距离都不超过$L$的点在树上是一个连通块，考虑在每种方案对应的离$1$最近的点统计。

即对于每个点$x$，统计离它距离不超过$L$的点数$call[x]$，再减去离它和它父亲距离都不超过$L$的点数$cext[x]$，然后用组合数计算方案数。

对于$call[x]$可以通过点分治+排序双指针$O(n\log^2n)$统计。

对于$cext[x]$，注意到$cext[x]=call[x]-csub[x]$，其中$csub[x]$表示$x$点子树中深度在$(dep[x]+L-dis(x,fa[x]),dep[x]+L]$的点数，二维数点问题，扫描线+树状数组维护即可$O(n\log n)$统计。

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

#include
     
      #include
      
       using namespace std;typedef long long ll;const int N=100010,P=1000000007;int n,K,L,i,j,x,y,z,fac[N],inv[N],ans;int g[N],nxt[N<<1],v[N<<1],w[N<<1],ok[N<<1],ed,son[N],f[N],all,now;int call[N],csub[N],cnt,bit[N],st[N],en[N],dfn;struct E{ll x;int y;E(){}E(ll _x,int _y){x=_x,y=_y;}}e[N],q[N<<1];inline bool cmp(const E&a,const E&b){return a.x
       
        f[x])f[x]=son[v[i]];  }  if(all-son[x]>f[x])f[x]=all-son[x];  if(f[x]
        
         L)j--;    call[e[i].y]+=p*j;  }}void solve(int x){  int i;  cnt=0;  dfs(x,0,0);  cal(1);  for(i=g[x];i;i=nxt[i])if(ok[i]){    cnt=0;    dfs(v[i],x,w[i]);    cal(-1);  }  for(i=g[x];i;i=nxt[i])if(ok[i]){    ok[i^1]=0;    f[0]=all=son[v[i]];    findroot(v[i],now=0);    solve(now);  }}void dfs2(int x,int y,ll z){  st[x]=++dfn;  e[x]=E(z,x);  q[++cnt]=E(z+L,x);  for(int i=g[x];i;i=nxt[i])if(v[i]!=y){    q[++cnt]=E(z+L,-v[i]);    dfs2(v[i],x,z+w[i]);  }  en[x]=dfn;}inline void ins(int x){for(;x<=n;x+=x&-x)bit[x]++;}inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}inline int C(int n,int m){return n
         
          0)csub[x]+=y;else csub[x]-=y;  }  for(fac[0]=i=1;i<=n;i++)fac[i]=1LL*fac[i-1]*i%P;  for(inv[0]=inv[1]=1,i=2;i<=n;i++)inv[i]=1LL*(P-inv[P%i])*(P/i)%P;  for(i=2;i<=n;i++)inv[i]=1LL*inv[i-1]*inv[i]%P;  for(i=1;i<=n;i++)ans=((ans+C(call[i],K))%P+P-C(call[i]-csub[i],K))%P;  ans=1LL*ans*fac[K]%P;  printf("%d",ans);}
         
        
       
      
     

　　

B. Card Game

枚举$n$的所有约数判断。

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

　　

C. The Most Expensive Gift

若循环节长度为$1$，则答案下界为$\frac{n^2}{9}$，经过分析可得循环节长度超过$8$都是不优的。

暴力搜索所有长度不超过$8$的串作为循环节，然后贪心匹配计算长度即可。

时间复杂度$O(3^8n)$。

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

　　

D. Cut the Cake

两个维度独立，对于一维问题，将所有位置排序，每隔$k$个切一刀即可。

#include
     
      const int N=300;int n,m,k,i,j,dx,dy,cntx,cnty,cx[N],cy[N],qx[N],qy[N];char a[N][N];inline int cal(int xl,int xr,int yl,int yr){	int t=0;	for(int i=xl;i<=xr;i++)for(int j=yl;j<=yr;j++)if(a[i][j]=='1')t++;	return t;}int main(){	scanf("%d%d%d",&n,&m,&k);	for(i=1;i<=n;i++)scanf("%s",a[i]+1);	for(i=1;i<=n;i++)for(j=1;j<=m;j++)if(a[i][j]=='1'){		dx++;		if(dx%k==0&&dx
     

　　

E. Message

留坑。

 

F. Bad Word

若整个串不是回文串，则答案显然为$1$。

若整个串形如$aaaaa$、$aabaa$、$ababa$，则无解。

否则答案必然是$2$。

#include
     
      const int N=200010;int n,i;char a[N];int main(){	scanf("%d%s",&n,a+1);	for(i=1;i<=n;i++)if(a[i]!=a[n-i+1])break;	if(i<=n)return puts("1"),0;	for(i=1;i<=n;i++)if(a[i]!=a[1])break;	if(i>n)return puts("-1"),0;	if(n%2==0)return puts("2"),0;	for(i=1;i<=n/2;i++)if(a[i]!=a[1])break;	if(i>n/2)return puts("-1"),0;	for(i=1;i<=n;i++){		if(i>2&&a[i]!=a[i-2])break;	}	if(i>n)return puts("-1"),0;	puts("2");}
     

　　

G. Zenyk, Marichka and Interesting Game

首先将所有石子数都模$A+B$，并剔除小于$\min(A,B)$的堆。

若$A=B$，则根据奇偶性判断即可。

若$A>B$，枚举$A$的第一步行动，然后交换先后手，转化为$A<B$的问题。

若$A<B$：

• 若$n=0$，则先手必败。
• 若一步之内可以造出只能$A$拿的堆，即存在石子数$<B$或者$\geq 2A$的堆，那么$A$可以利用这一堆来控制先后手，从而必胜。
• 否则任何一堆两人都只能恰好拿一次，故根据$n$的奇偶性判断即可。

#include
     
      #include
      
       #include
       
        using namespace std;typedef pair
        
         P;const int N=100010;int n,m,A,B,x,a[N];set
         
T;int work(int A,int B){	if(T.size()==0)return 0;	set
         
::iterator x=T.begin();	if(x->first
          
           first>=A*2)return 1; return T.size()%2;}int solve(){ int i,ans=0; if(A==B){ for(i=1;i<=m;i++)ans=(ans+a[i]/A)%2; return ans; } if(A
           
            =A){ T.erase(P(a[i],i)); int t=a[i]-A; if(t
            
           
          
        
       
      
     

　　

H. Frog Jumping

贪心用代价最小的若干个青蛙去贪心地走路线。

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

　　

I. Slot Machine

按照最坏情况模拟即可。

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

　　

J. Half is Good

注意到边权在$[0,2^{62})$内随机，故最后$8$位影响排序结果的概率非常小，可以忽略。

还剩$54$位，分成最高的$22$位和后面$32$位，将最高的$22$位相同的边分组，每组内部排序，每组数量都不多。

然后直接求最小生成树即可。

#include
     
      #include
      
       using namespace std;typedef unsigned int U;typedef unsigned long long ll;const int N=10000010,M=(1<<22)+5;int n,m,i,u,v,f[N],have,goal;int g[M],nxt[N],q[1000000];U e[N][3],ans[N/32+10];U s;ll w;inline bool cmp(int x,int y){return e[x][2]
       
        << 13;s ^= s >> 17;s ^= s << 5;return s;}int F(int x){return f[x]==x?x:f[x]=F(f[x]);}inline void merge(int x){	int a=e[x][0],b=e[x][1];	//printf("merge %d %d\n",a,b);	if(F(a)!=F(b)){		have++;		ans[x>>5]|=1U<<(x&31);		f[f[a]]=f[b];	}}inline void solve(int x){	if(g[x]<0)return;	if(nxt[g[x]]<0){		merge(g[x]);		return;	}	int cnt=0;	for(int i=g[x];~i;i=nxt[i])q[cnt++]=i;	sort(q,q+cnt,cmp);	for(int i=0;i
        
         >2;		w=w*getnxt();		w>>=8;		e[i][0]=u;		e[i][1]=v;		e[i][2]=w&mask;		w>>=32;		nxt[i]=g[w];		g[w]=i;		//printf("%d %d %llu\n",u,v,w);	}	for(i=0;i
        
       
      
     

　　

K. Dance

留坑。

 

L. Impress Her

对于一个$A\times B$的包围矩形，因为四连通，至少消耗$A+B$个点，故直接枚举每个矩形内部所有点的时间复杂度为$O(n^3)$。

对于每个点记录其所属矩形，对于每个矩形$x$，枚举内部所有点，检查$x$是否包含该点所属矩形即可，用时间戳来$O(1)$判重。

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