凑平方数

把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。 比如：0, 36, 5948721

再比如： 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等…

注意，0可以作为独立的数字，但不能作为多位数字的开始。 分组时，必须用完所有的数字，不能重复，不能遗漏。

如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？

注意：需要提交的是一个整数，不要填写多余内容。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
using namespace std;
typedef long long LL;
#define maxn (100005*2)
long long  table[maxn],cnt=0;int t=0;
/*
国赛的回溯题目，
没有注意到的地方就是对于x为0的处理，
在用while结构中，如果x为0，则过程直接被跳过了。。。
*/bool check(long long  x)
{int bo[10];memset(bo,0,sizeof(bo));while(x){if(bo[x%10]) return false;bo[x%10]=1;x/=10;}return true;
}void inittable(int N)
{for(long long  i=0;i<N;i++){if(!check(i*i)) continue;table[cnt++]=i*i;}
}int ans[10],result=0;
bool judge(long long x)
{while(x){if(ans[x%10]) return false;x/=10;}return true;
}bool judge()
{for(int i=0;i<10;i++)  if(!ans[i]) return false;return true;
}void make(long long  x)
{if(x==0) ans[0]=1;while(x){ans[x%10]=1;x/=10;}
}void muns(long long x)
{if(x==0) ans[0]=0;while(x){ans[x%10]=0;x/=10;}
}void dfs(int n)
{if(judge()){result++;return ;}if(n>=cnt) return ;for(int i=n;i<cnt;i++){if(!judge(table[i]))  continue;make(table[i]);dfs(i+1);muns(table[i]);}
}int main()
{inittable(100000);memset(ans,0,sizeof(ans));dfs(0);cout<<result<<endl;return 0;
}