sgu159 Self-Replicating Numbers DFS+高精

       通俗易懂的題意..給進制數B，長度n，求所有長度為n，并且平方後低n位不變的數..由于n是2000，存儲的過程要用到高精...n雖然很大，但實際上符合要求的數沒多少，是以直接暴力就好了，bfs,dfs都行，要注意的一點是，判斷的時候如果寫成n^2的高精乘法，會T掉，這裡必須優化一下。事實上，隻要低n位的話，我們每次添加新一位的時候隻要存兩個數就行，一個是這一位填多少，另一個是填上這個數後，對它高一位的影響，也就是進位的情況。在算下一位的時候，先O（n）掃描一遍算出目前數在最高位是多少，在加上上一次記錄的進位，如果這個和與這一位填的數相同，就是ok的..剛開始我寫的是個bfs，結果寫100多行還各種出錯，推倒後寫了個dfs不到60行直接1A了...還有一點，n==1的時候注意特判，0也是可行的

#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
int dt[2020];
int n,m;
vector<string> out;
int ans=0;
void save(int p[])
{
    string s;
    for (int i=n; i>=1; i--)
    if (p[i]<10) s+=(char(p[i]+'0'));
    else s+=(char(p[i]-10+'A'));
    out.push_back(s);
}
void dfs(int up,int k)
{
    for (int j=0; j<m; j++)
    {
        if (k==n && j==0) continue;
        dt[k]=j;
        int l=1;
        int r=k;
        int tmp=0,tp=0;
        while (l<=r)
        {
            if (l==r) tmp+=dt[l]*dt[r];
            else tmp+=2*dt[l]*dt[r];
            l++;
            r--;
        }
        if (((tmp+up) % m)==j)
        {
            if (k<n) dfs((tmp+up)/m,k+1);
            else save(dt),ans++;
        }
    }
}
int main()
{
//    freopen("in.txt","r",stdin);
    cin>>m>>n;
    ans=0;
    dfs(0,1);
    if (n==1)
    {
        ans++;
        out.push_back("0");
    }
    cout<<ans<<endl;
    for (int i=0; i<out.size(); i++)
    cout<<out[i]<<endl;
}