CF上的题考的就是思维啊,而这道题就是要用到十分巧妙的处理……
题意:给定一个素数作为一个正方阵的第一行,而下面几行都要补一个素数进去形成一个对称矩阵,即当前矩阵与转置后的矩阵相等。
如:239 9001
307 0002
977 0002
1223
思路:其实都是参照CF上某位大牛的……dp[i][j]的i表示一个数的第i+1位是空的,可以任意填一个个位数,而j表示的就是用0去代替这个空位的一个整数,dp[i][j]表示的就是这样的数的总的个数。g[i]表示的是第i行(由0开始)应该填的数。然后就是深搜了,这个函数处理的是在矩阵上两个对称的数,分别用0-9去填……好像讲得很乱,那就看代码吧!
#include<iostream> using namespace std; #define N 100000 int len,ans,b[10],g[10],dp[6][N]; void dfs(int r,int c) { int i,num; if(r==len) { num=1; for(i=1;i<len;i++)num*=dp[len-i-1][g[i]]; ans+=num; return; } if(c==len) { dfs(r+1,r+2); return; } for(i=0;i<10;i++) { g[r]+=i*b[len-c-1]; g[c]+=i*b[len-r-1]; dfs(r,c+1); g[r]-=i*b[len-c-1]; g[c]-=i*b[len-r-1]; } } int main() { //freopen("a.txt","r",stdin); int i,j,t,vis[N]; char s[10]; b[0]=1; for(i=1;i<7;i++)b[i]=b[i-1]*10; memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); for(i=2;i<N;i++) { if(i<316)for(j=i*i;j<N;j+=i)vis[j]=1; //快速求素数 if(!vis[i]) for(j=0;j<6;j++)dp[j][i/b[j+1]*b[j+1]+i%b[j]]++; } scanf("%d",&t); while(t--) { scanf("%s",s); len=strlen(s); g[0]=0; for(i=0;i<len;i++)g[0]=g[0]*10+s[i]-'0'; for(i=1;i<len;i++)g[i]=(s[i]-'0')*b[len-1]; ans=0; dfs(1,2); printf("%d\n",ans); } return 0; }