luogu P3896 [湖南集训]Clever Rabbit

大佬教程收集整理的这篇文章主要介绍了luogu P3896 [湖南集训]Clever Rabbit，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

题面传送门 首先爆枚每个数肯定是不行的。 考虑优化，我一开始写的是搜(g)然后判断是否可行。这样的大概是(10^7)中情况。 然而还要乘个(n)，复杂度铁定爆炸，卡常卡到(4.4s)实在卡不动。 然后发现其实(f)的左右两边是互为相反数的，只要搜一半即可。 时间复杂度(O(nC_{9}^{frac{n}{2}})) code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(X) ((X)>0?(X):-(X))
#define re register
#define ll long long
#define db double
#define N 30
#define M 200000
#define mod 998244353
#define eps (1e-7)
#define U unsigned int
#define IT set<ques>::iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(X))
using namespace std;
int n,m,f[N+5],G[N+5],A[N+5],B[N+5],C[N+5],Ah;ll p,Ans,ToT;
I void check(){
	rE int i,j;Ah=n;A[m+1]=0;for(i=9;~i;i--) for(j=1;j<=f[i];j++) A[Ah--]=i;for(i=1;i<=m;i++) A[i]=-A[n-i+1]; 
	for(i=1;i<=n;i++) A[i]<0&&(A[i+1]--,A[i]+=10),G[A[i]]++,B[i]=A[i];
	Ah=0;for(i=9;~i;G[i--]=0)while(G[i]--) B[++Ah]+=i,B[Ah+1]+=B[Ah]/10,B[Ah]%=10,C[n-Ah+1]=i;
	for(i=1;i<=n;i++) if(B[i]!=C[i])return;for(ToT=0,i=n;i;i--) ToT=(ToT*10+A[i])%p;Ans+=ToT*ToT%p;//for(i=n;i;i--) printf("%d",A[i]);printf("n");
}
I void dfs(int x,int w){
	if(x==9)return f[x]=m-w,check();rE int i;
	for(i=0;i<=m-w;i++) f[x]=i,dfs(x+1,w+i);
} 
int main(){
	freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	rE int i;scanf("%d%lld",&n,&p);m=n>>1;dfs(0,0);printf("%lldn",Ans%p);
}

大佬总结

以上是大佬教程为你收集整理的luogu P3896 [湖南集训]Clever Rabbit全部内容，希望文章能够帮你解决luogu P3896 [湖南集训]Clever Rabbit所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。