本文共 7369 字，大约阅读时间需要 24 分钟。

总结

\(T1\) 和 \(T2\) 考试的时候感觉不太可做，就打了两个暴力

其实最后的算法还是很简单的，\(bfs\) 和 \(dfs\) 大概是 \(noip\) 的知识

总之就是把题目想复杂了，没有做出来

\(T3\) 的话发现 \(p\) 的值只有两个，于是果断打表

\(p=2\) 的很快就看出来了

\(p=2017\) 的看了一会也发现了规律，就是把所有 \(+1\) 后模 \(2017\) 等于 \(0\) 的质数筛出来

然后它们的倍数都是合法的，但是发现 \(n\) 比较大的时候会有少算的情况

又把 \(5340721,12008989,13980121,139405249\) 加了进去

当时就感觉假了，不过还是把 \(10^8\) 以内的跑对了

看了题解之后发现确实有少算的情况

总之还是要加强推式子的能力

A. Colorado Potato Beetle

分析

暴力就是把所有的点加进去跑一个 \(bfs\)

但是 \(10^9\) 的数据肯定跑不动

正解是离散化后跑 \(bfs\)

离散化后的一个点代表以它为左上角的矩形

把一个线段拆成两个点，把每个点左边和右边的点也放进去，避免一些奇奇怪怪的特判

代码

#include
   
    #include
    
     #include
     
    
   

B. Distinct Paths

分析

暴力做法直接大力搜索即可

正解是优化后的搜索

注意到当 \(n+m-1>k\) 时一定是无解的

因为种类最少的放法就是每一个对角线放一种颜色

如果颜色数小于对角线的条数肯定无解

而 \(k \leq 10\)，所以 \(n+m \leq 11\)

加两个剪枝就能过了

\(1\)、如果当前点到终点的步数大于颜色的方案数，直接返回 \(0\)

\(2\)、维护每种颜色的出现次数(开始就赋予的颜色也算在内),所有此时第一次出现的颜色就可以算作同种情况，记录一下就行了

代码

#include
   
    #define rg registerinline int read(){	rg int x=0,fh=1;	rg char ch=getchar();	while(ch<'0' || ch>'9'){		if(ch=='-') fh=-1;		ch=getchar();	}	while(ch>='0' && ch<='9'){		x=(x<<1)+(x<<3)+(ch^48);		ch=getchar();	}	return x*fh;}const int maxn=1e3+5,mod=1e9+7;int a[maxn][maxn],vis[maxn],n,m,k,zt[maxn][maxn];int js(rg int zt){	rg int ncnt=0;	for(rg int i=1;i<=k;i++){		if(zt&(1<<(i-1))) ncnt++;	}	return ncnt;}int dfs(rg int nx,rg int ny){	if(nx==n+1) return 1;	rg int nzt=(zt[nx-1][ny]|zt[nx][ny-1])^((1<
    
     js(nzt)) return 0;	for(rg int i=1;i<=k;i++){		if((nzt&(1<<(i-1))) && (a[nx][ny]==0 || a[nx][ny]==i)){			zt[nx][ny]=zt[nx-1][ny]|zt[nx][ny-1]|(1<<(i-1));			vis[i]++;			if(vis[i]==1){				if(tmp==-1) tmp=dfs(nx+(ny==m),ny==m?1:ny+1);				ans=(ans+tmp)%mod;			} else {				ans=(ans+dfs(nx+(ny==m),ny==m?1:ny+1))%mod;			}			vis[i]--;		}	}	return ans;}int main(){	n=read(),m=read(),k=read();	for(rg int i=1;i<=n;i++){		for(rg int j=1;j<=m;j++){			a[i][j]=read();			vis[a[i][j]]++;		}	}	if(n+m-1>k){		printf("0\n");		return 0;	}	printf("%d\n",dfs(1,1));	return 0;}
    
   

C. 不好不坏题

分析

因为约数和是积性函数，设 \(f(n)\) 为 \(n\) 的约数和

如果 \(n=\prod p_i^{a_i}\)

那么 \(f(n)=\prod f(p_i^{a_i})\)

\(p\) 的取值只有两种，所以分类讨论

当 \(p=2\) 时

我们只需要判断 \(f(n)\) 的奇偶性就可以了

显然，如果 \(f(p_i^{a_i})\) 中有一个为偶数，那么答案就是偶数

也就是说，只有当 \(f(p_i^{a_i})\) 全为奇数时，答案才不是偶数

我们只需要算出总答案，然后把这些答案不是偶数的贡献减去就行了

对于除了 \(2\) 之外的所有质数，当它们的指数是偶数时，它们的约数和一定是奇数

对于 \(2\) 来说，它的任何次幂都是奇数

所以最后的答案一定是 \(2^k\) 乘一个平方数

当 \(k=0\) 时，答案就是平方数

当 \(k=1\) 时，答案就是平方数乘 \(2\)

当 \(k=2\) 时，答案又可以看作一个平方数

所有最终的答案就是总贡献减去平方数和平方数的二倍的贡献

当 \(p=2017\) 时

我们需要找出所有 \(f(p_i^{a_i})\%2017=0\) 的质数

不妨枚举指数 \(a_i\)

当 \(a_i\) 等于 \(1\) 时，我们要找的就是 \((p+1)\% 2017=0\) 的所有质数

因为 \(p\) 肯定是一个奇数，所以我们可以把 \(4034\) 作为一个循环节去枚举，判断 \(p\) 是不是质数

如果是，就累加这个数和这个数所有倍数的贡献

判断质数要用 \(Miller\_Robin\) ，根号筛会 \(T\) 飞

当 \(a_i\) 等于 \(2\) 时，要找满足 \(p^2+p+1\% 2017=0\) 的所有质数

因为有平方这个限制，所以直接从根号开始枚举

当 \(a_i\) 等于 \(3\) 时，只有 \(229\) 满足条件

当 \(a_i\) 更大的时候就没有数满足了

但是这样做还是不对的

因为会有以下两种情况

\(1\)、因为约数个数和不是完全积性函数，所以 \(f(p^2)\) 不等于 \(f(p)^2\) ，但是当我们枚举倍数的时候，有可能会枚举到 \(p^2\),\(p^3\)

所以要把这个贡献减去

当 \(a_i=2\) 时，最小的质数是 \(2311\)，它的三次方是 \(12342406231\)，已经超过了 \(n\) 的最大值，所以不用考虑

其它两种情况都要减去

\(2\)、有的贡献会被多计算

比如当 \(a_i=1\) 时，\(12101\) 和 \(24203\) 都是满足条件的

我们在枚举 \(12101\) 时，会计算 \(12101 \times 24303\) 的贡献

在枚举 \(24303\) 时，也会计算 \(12101 \times 24303\) 的贡献

所以要减去其中的一个

这道题还是有一点卡常的

首先，\(Miller\_Robin\) 里一定要用光速乘

ll gsc(rg ll ds,rg ll zs,rg ll Mod){	return ((unsigned long long)(ds*zs)-(unsigned long long)((long double)ds/Mod*zs)*Mod+Mod)%Mod;}

原理就是 \(a\%b=a-a/b \times b\)

首先我们把 \(ds \times zs / Mod\) 的值存到 \(long\ double\) 里，这个值比较小是不会爆的

然后利用 \(ds \times zs -ds \times zs /Mod \times Mod\) 的值不会大于 \(Mod\) ，直接存到 \(unsigned\ long\ long\) 自然溢出就行了

还有就是在进行 \(Miller\_Robin\) 之前判断一下这个数能不能被一些小质数整除，如果能，直接返回 \(false\) 就行了

代码

#include
   
    #include
    
     #include
     
      #define rg registerinline int read(){	rg int x=0,fh=1;	rg char ch=getchar();	while(ch<'0' || ch>'9'){		if(ch=='-') fh=-1;		ch=getchar();	}	while(ch>='0' && ch<='9'){		x=(x<<1)+(x<<3)+(ch^48);		ch=getchar();	}	return x*fh;}const int mod=1e9+7,ny2=500000004,maxn=1e7+5,times=4,chk[10]={0,2,3,5,7};typedef long long ll;int p,ans,tmp,pri[maxn],mmax,tp;bool not_pri[maxn];ll n,sta[maxn];void xxs(){	not_pri[0]=not_pri[1]=1;	for(rg int i=2;i<=mmax;i++){		if(!not_pri[i]){			pri[++pri[0]]=i;		}		for(rg int j=1;j<=pri[0] && i*pri[j]<=mmax;j++){			not_pri[i*pri[j]]=1;			if(i%pri[j]==0) break;		}	}}ll gsc(rg ll ds,rg ll zs,rg ll Mod){	return ((unsigned long long)(ds*zs)-(unsigned long long)((long double)ds/Mod*zs)*Mod+Mod)%Mod;}ll ksm(rg ll ds,rg ll zs,rg ll Mod){	rg ll nans=1;	while(zs){		if(zs&1LL) nans=gsc(nans,ds,Mod);		ds=gsc(ds,ds,Mod);		zs>>=1LL;	}	return nans;}bool check(rg ll a,rg ll r,rg ll t,rg ll Mod){	ll nans=ksm(a,r,Mod),tmp=nans;	for(rg ll i=1;i<=t;i++){		nans=gsc(tmp,tmp,Mod);		if(nans==1 && tmp!=1 && tmp!=Mod-1) return 0;		tmp=nans;	}	if(tmp==1) return 1;	else return 0;}bool Miller_Robin(rg ll val){	if(val<=mmax) return !not_pri[val];	if(val<2 || (val&1LL)==0 || val%3==0 || val%5==0 || val%7==0) return 0;	rg ll t=0,r=val-1;	while((r&1LL)==0){		r>>=1;		t++;	}	for(rg int i=1;i<=times;i++){		if(!check(chk[i],r,t,val)) return 0;	}	return 1;}long long js(rg long long val){	rg long long cnt=n/val%mod;	return (cnt+1)*cnt/2*val%mod;}void solve2(){	mmax=1e7;	xxs();	for(rg long long i=4033;i<=n;i+=4034){		if(Miller_Robin(i)) sta[++tp]=i;	}	for(int i=1;i<=tp;++i){		for(int j=1;j<=i&&sta[j]*sta[i]<=n;++j){			ans=(ans-js(sta[i]*sta[j])+mod)%mod;		}	}	ans=(ans-js(229LL*229*229*229)+mod)%mod;	rg ll sqr=sqrt(n);	for(rg ll i=1;i<=sqr;i++){		if(Miller_Robin(i) && (i*i+i+1)%p==0){			sta[++tp]=i*i;		}	}	sta[++tp]=229LL*229*229;	for(rg int i=1;i<=tp;i++){		ans+=js(sta[i]);		if(ans>=mod) ans-=mod;	}	printf("%d\n",ans);}void solve1(){	ans=1LL*((n+1)%mod)*(n%mod)%mod*ny2%mod;	for(rg long long i=1;i*i<=n;i++){		tmp=i%mod;		ans-=1LL*tmp*tmp%mod;		ans=(ans+mod)%mod;		if(i*i*2<=n){			tmp=i%mod;			ans-=2LL*tmp*tmp%mod;			ans=(ans+mod)%mod;		}	}	printf("%d\n",ans);}int main(){	scanf("%lld%d",&n,&p);	if(p==2) solve1();	else solve2();	return 0;}
     
    
   

转载地址：http://qzvyz.baihongyu.com/