【洛谷3896】[湖南集训] Clever Rabbit（搜索）

点此看题面

• 定义(g(x))表示将(x)各位数码从大到小排序后构成的数字，(h(x))表示将(x)各位数码从小到大排序后构成的数字。
• 求所有满足(x=g(x)-h(x))的(n)位数(x)的平方和。
• (nle30)

非打表的(dfs)做法

显然这道题目(nle30)完全可以打表做，这里就不多说了。

考虑在不借位（即每一位的数可以小于(0)）的情况下肯定满足第(i)位与第(n-i+1)位互为相反数，且从高到低每一位降序。

因此我们可以直接枚举一个长为(lfloorfrac n2 floor)的降序序列，先对它进行一轮借位操作求出(x)，然后计算(g(x)-h(x))检验即可。

代码：(O(nC_{lfloorfrac n2 floor+9}^9))

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 30
using namespace std;
int n,ans,X,p[N+5],s[N+5],s1[N+5],s2[N+5];I void Check()
{
	RI i,j;for(i=1;i<=n;++i) s[i]=p[i];for(i=1;i<=n;++i) s[i]<0&&(s[i]+=10,--s[i+1]),s1[i]=s[i];//一轮借位还原出x
	for(sort(s1+1,s1+n+1),i=1;i<=n;++i) s2[n-i+1]=s1[i];//求出g(x)和h(x)
	for(i=1;i<=n;++i) if((s1[i]-=s2[i])<0&&(s1[i]+=10,--s1[i+1]),s1[i]^s[i]) return;//比较g(x)-h(x)与x
	RI t=0;for(i=n;i;--i) t=(10LL*t+s[i])%X;ans=(ans+1LL*t*t)%X;//符合条件，统计答案
}
I void dfs(CI x=1,CI v=9)//枚举长为n/2的降序序列
{
	if(x>n/2) return Check();for(RI i=v;~i;--i) p[x]=-i,p[n-x+1]=i,dfs(x+1,i);
}
int main()
{
	return scanf("%d%d",&n,&X),dfs(),printf("%d
",ans),0;
}