求\(\sum k_ix_i^{p_i}=0\)的整数解个数

当时是把这个式子拆成两半，然后两边合并

这题与其类似

每次搜索一半，然后两半合并

代码中PreDo()函数的作用是划定单次搜索所用的数

设左边某次搜索得到数为\(x_1\)，右边的数为\(x_2\)，得到某数\(i\)的排列数记为\(T_i\)

那么，若 \((10^{n-\frac{n}{2}}x_1+x_2) \mod D = 0\) ，那么就给答案加上 \(T_{x_1}\times T_{x_2}\)

下面是AC Code

cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXD=1005; int Dat[10],TDat[10]; int Ans[2][MAXD];//表示余数 int D; int Ret; char buf[20]; int n; void PreDo(int,int); void Dfs(int,int,int); void Solute(); //-- void PreDo(int deep,int sel) { if (deep>=n/2) Solute(); else { for (int i=sel;i<10;i++) { if (TDat[i]<Dat[i]) { TDat[i]++; PreDo(deep+1,i); TDat[i]--; } } } } void Dfs(int deep,int x,int type) { if (deep==0) Ans[type][x%D]++; else for (int i=0;i<10;i++) if (TDat[i]) { TDat[i]--; Dfs(deep-1,x*10+i,type); TDat[i]++; } } void Solute() { memset(Ans,0,sizeof(Ans)); Dfs(n/2,0,0); for (int i=0;i<10;i++) TDat[i]=Dat[i]-TDat[i]; Dfs(n-n/2,0,1); for (int i=0;i<10;i++) TDat[i]=Dat[i]-TDat[i]; int Size=1; for (int i=1;i<=n-n/2;i++) Size*=10; for (int i=0;i<D;i++) Ret+=Ans[0][i]*Ans[1][(D-(i*Size)%D)%D]; } //-- void MAIN() { memset(Dat,0,sizeof(Dat)); memset(TDat,0,sizeof(TDat)); scanf("%s",buf);n=strlen(buf); scanf("%d",&D); for (int i=0;i<n;i++) Dat[buf[i]-'0']++; Ret=0;PreDo(0,0); printf("%d\n",Ret); } //-- int main() { int T; scanf("%d",&T); while (T--) MAIN(); return 0; } d