题意：待补充..O_Ob
分析：
20%：枚举所有可能的置换群（排列集合），判断是否满足要求。O(n！^m)
没见过这么难写的暴搜，我真是太年轻。。
伪代码：
1 2 3 4 5 6 7 8 9 10 | void dfs(int x){ if(x==m+1){ans++;return;} F(i,1,n!){//枚举所有可能为第x个的"元素" 判断与前面位置的元素是否相容; //1:是否满足B矩阵(对于"元素") //2:是否与之前元素相同 if(ok) dfs(x+1); }} |
代码，关键是用到了next_permutation函数：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 | //4:35-5:45const int N=6,M=5;int n,m,ans;int T[N],a[M][N],B[M][M];bool check(int x,int y,int b){ F(i,1,n) T[i]=a[y][a[x][i]]; F(i,1,n) if(T[i]!=a[b][i]) return false; return true;}void dfs(int x){ if(x==m+1){ans=(ans+1)%MOD;return;} do{ bool ok=1; F(i,1,x) F(j,1,x)//判断1 if(B[i][j]<=x && !check(i,j,B[i][j])){ok=0;break;} if(!ok) continue; F(i,1,x-1){//判断2 bool diff=0; F(j,1,n) if(a[i][j]!=a[x][j]) diff=1;//与之前的"排列"是否完全相同. if(!diff){ok=0;break;} } if(ok) dfs(x+1); }while(next_permutation(a[x]+1,a[x]+n+1));//相当于是枚举的过程,不需要写成递归了! }int main(){ int tt=read(); while(tt--){ n=read();m=read();ans=0; F(i,1,m) F(j,1,m) B[i][j]=read(); F(i,1,m) F(j,1,n) a[i][j]=j;//初始化为最小排列 dfs(1); printf("%d\n",ans%MOD); } return 0;} |
评论 (0)
