A. City Wall

找规律。

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

　　

B. Domino Colorings

若已经知道了每个格子的颜色，那么可以DP判断是否能由某种骨牌铺成，设$dp[S]$表示轮廓线上$n$个点匹配状态为$S$是否可行即可。

现在不知道每个格子的颜色，那么需要DP这些颜色，设$f[i][j][c][v]$表示考虑到$(i,j)$，轮廓线上$n$个点颜色为$c$，$dp[S]$这个大小为$2^n$的布尔数组取值为$v$时的方案数。

当$n=6$时状态数也只有不到$2000$个，所以可以通过。

#include
     
      #include
      
     

　　

C. Counterquestion

暴力枚举$10!$种大小关系，然后求出每种的方案数即可。

#include
     
      #include
      
       #include
       
        using namespace std;typedef long long ll;const int N=500;int n,i,j,m,q[N],id[N],cnt,rk[N];char a[N];ll f[5000000];void write(ll S){	static ll w[1000];	for(int i=n-1;i;i--){		w[i]=S%3;		S/=3;	}	for(i=1;i
        
         ');		putchar(' ');	}	putchar(a[n]);}int main(){	scanf("%s",a+1);	n=strlen(a+1);	for(i=1;i<=n;i++){		if(!id[a[i]])id[a[i]]=++m;	}	for(i=1;i<=m;i++)q[i]=i;	do{		for(i=1;i<=m;i++)rk[q[i]]=i;		ll cur=0;		for(i=1;i
        
       
      
     

　　

D. Galaxy Center

首先假设$A$在$B$外层或同层，不然可以交换$AB$。

若$A$和$B$同层且距离不超过$5$，则此时直接走过去最优。

否则最优方案一定是将$A$往里走一层。

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

　　

E. IBM 1403

预处理出$f[i][j]$表示模式串第$i$个位置之后第一个字符$j$的位置，对于每一行计算需要的最大时间即可。

#include
     
      #include
      
       #include
       
        using namespace std;const int N=1000010;typedef long long ll;int L,n,i,j,cur,f[100010][130];char a[N],b[N];ll ans;int main(){	gets(a);	L=strlen(a);	for(i=L-1;~i;i--)f[L][a[i]]=i;	for(i=L-1;~i;i--){		for(j=0;j<130;j++)f[i][j]=f[i+1][j];		f[i][a[i]]=i;	}	while(gets(b)){		n=strlen(b);		int tmp=0;		for(i=0;i
        
         tmp)tmp=nxt;		}		tmp++;		ans+=tmp;		cur=(cur+tmp)%L;	}	printf("%lld",ans);}
        
       
      
     

　　

F. Line Tracing

留坑。

 

G. The Queen and the Knight

当$n\leq 30$时，可以$O(n^5)$BFS出所有局面下的最优策略。

当$n>30$时，可以先逼近骑士，然后分类构造。

 

H. Product of Roots

\[\begin{eqnarray*}

f(x)&=&\prod_{i=1}^n(1+a_ix)\\

&=&\exp\left(\sum_{i=1}^n\ln(1+a_ix)\right)

\end{eqnarray*}\]

将$\ln(1+a_ix)$泰勒展开，有：

\[\begin{eqnarray*}

f(x)&=&\exp\left(\sum_{i=1}^n\ln(1+a_ix)\right)\\

&=&\exp\left(\sum_{i=1}^n\sum_{j\geq 1}\frac{(-1)^{j+1}}{j}x^ja_i^j\right)\\

&=&\exp\left(\sum_{j\geq 1}\frac{(-1)^{j+1}}{j}x^j\sum_{i=1}^n a_i^j\right)\\

&=&\exp\left(\sum_{j\geq 1}\frac{(-1)^{j+1}}{j}x^jA_j\right)\\

\end{eqnarray*}\]

对于$g$和$h$同理，则：

\[\begin{eqnarray*}

g(x)&=&\exp\left(\sum_{j\geq 1}\frac{(-1)^{j+1}}{j}x^jB_j\right)\\

h(x)&=&\exp\left(\sum_{j\geq 1}\frac{(-1)^{j+1}}{j}x^j\sum_{i=1}^n\sum_{k=1}^m a_i^jb_k^j\right)\\

&=&\exp\left(\sum_{j\geq 1}\frac{(-1)^{j+1}}{j}x^j\sum_{i=1}^n a_i^j\sum_{k=1}^m b_k^j\right)\\

&=&\exp\left(\sum_{j\geq 1}\frac{(-1)^{j+1}}{j}x^jA_jB_j\right)\\

&=&\exp\left(\sum_{j\geq 1}\frac{(-1)^{j+1}}{j}x^jC_j\right)

\end{eqnarray*}\]

多项式$\ln$求出所有$A_i$和$B_i$，令$C_i=A_iB_i$，然后按上式用多项式$\exp$计算$h$即可。

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

#include
     
      typedef long long ll;const int N=262144,K=17;int n,m,i,k,_;int a[N+10],b[N+10],c[N+10],tmp[N+10],tmp2[N+10];int P=998244353,G=3,g[K+1],ng[K+10],inv[N+10],inv2;inline int pow(int a,int b){int t=1;for(;b;b>>=1,a=(ll)a*a%P)if(b&1)t=(ll)t*a%P;return t;}inline void NTT(int*a,int n,int t){  for(int i=1,j=0;i
      
       >=1,~j&s;);    if(i
       
        =P)B-=P;      w=(ll)w*_w%P;    }  }  if(t==-1)for(int i=0,j=inv[n];i
        
         >1);  int k=n<<1,i;  for(i=0;i
         
          >1);  getln(b,tmp,n);  int k=n<<1,i;  for(i=0;i
          
           <0)tmp[i]+=P;} if((++tmp[0])==P)tmp[0]=0; for(i=n;i
          
         
        
       
      
     

　　

I. Safe Landing

按题意模拟。

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

　　

J. Perfect Square

取$20$个大质数，然后检查$x^2\bmod p=n$是否有解即可。

根据二次剩余，这等价于$n^{\frac{p-1}{2}}\bmod p=1$。

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;const int N=1000010;int n,i,cnt;char a[N];bool isprime(int n){	for(int i=2;i<=n/i;i++)if(n%i==0)return 0;	return 1;}ll powmod(ll a,ll b,ll P){	ll t=1;	for(;b;b>>=1,a=a*a%P)if(b&1)t=t*a%P;	return t;}bool work(ll n,ll p){	if(n==0||n==1)return 1;	if(powmod(n,p>>1,p)!=1)return 0;	return 1;}bool check(int P){	ll ret=0;	for(int i=1;i<=n;i++)ret=(ret*10+a[i]-'0')%P;	return work(ret,P);}int main(){	scanf("%s",a+1);	n=strlen(a+1);	for(i=1000000000;;i++)if(isprime(i)){		if(!check(i))return puts("No"),0;		cnt++;		if(cnt>=20)return puts("Yes"),0;	}}