[20170517 ADV]排列组合

// 20170517adv.cpp:排列组合
#include "stdafx.h"
#include <stdio.h>
int N;//[3,7]
int M;//[3,6]
int a[7];
int b[6];
int mark[7];
int tbl[5040][6];
int idx;
int count;

void initialize(void)
{
   int i,j;
   for(j=0;j<N;j++)
   {
      a[j]=-1;
      mark[j]=0;
   }
   for(j=0;j<M;j++)
      b[j]=-1;
   for(i=0;i<5040;i++)
      for(j=0;j<6;j++)
         tbl[i][j]=-1;

   scanf("%d %d",&N,&M);
   for(j=0;j<N;j++)
      scanf("%d",&a[j]);
   idx=0;
   count=0;
}

int search_table(void)
{
   int i,j;
   for(i=0;i<idx;i++)
   {
      for(j=0;j<M;j++)
      {
         if(b[j]!=tbl[i][j])
            break;
         if(j==M-1)
            return 1;
      }
   }
   return 0;
}

void bracelet_combination(int step)
{
   int i,j;
   int found;
   if(step==M)
   {
      found=0;
      found=search_table();
      if(found!=1)
      {
         for(i=0;i<M;i++)
         {
            for(j=0;j<M;j++)
            {
               tbl[idx][j]=b[(i+j)%M];
            }
            idx++;
         }
         count++;
      }
      return;
   }
   for(i=0;i<N;i++)
   {
      if(mark[i]==0)
      {
         b[step]=a[i];
         mark[i]=1;
         bracelet_combination(step+1);
         mark[i]=0;
      }
   }
   return;
}


int _tmain(int argc, _TCHAR* argv[])
{
   int t,test_case;
   freopen("20170517in.txt","r",stdin);
   scanf("%d", &test_case);
   for(t=1;t<=test_case;t++)
   {
      initialize();
      bracelet_combination(0);
      printf("#%d %d\n",t,count);
   }
   return 0;
}

/* input
5
3 3
1 2 3
4 4
1 2 2 3
5 5
5 6 5 7 8
6 4
3 3 3 4 4 4
7 6
2 3 1 5 4 6 8
*/

/* output
2
3
12
4
840
*/