/*
Chad Brewbaker
March 2, 2003

circularArrayCount.cpp

This program enumerates how many length N necklaces exist over an R letter alphabet where each bead is equal, or more than one away from it's neighbors. 


We do this by fixing the necklace at the color 0.  We then grow the necklace by incramenting the number of color states that exist at each position.

Example:
Alphabet=0,1,2,3,4

0:1-> 0:1,2:1,3:1 -> 0:3,1:1,2:2,3:2,4:1 -> ...

Where 0:1 means the zero state exists one time.




With fixed beads:
R*# of 0's

Divide by N to get rid of rotations?



*/

#include <iostream.h>
#include <math.h>


long ARR[50];
long NEW_ARR[50];

long N;
long R;

void incArray()
{
  long i,j;
 
  for(i=0;i<R;i++)
    NEW_ARR[i]=0;
  
  //increment everything by ARR[i]. Subtract from neighbors.
  for(i=0;i<R;i++)
    {
      for(j=0;j<R;j++)
	NEW_ARR[j]+=ARR[i];
      NEW_ARR[((i-1)+R)%R]-=ARR[i];
      NEW_ARR[(i+1)%R]-=ARR[i];
    }
  for(i=0;i<R;i++)
    ARR[i]=NEW_ARR[i];
  return;
}


int main()
{
  long i,j,k;  
  long sum;
  cout <<"\n Input n, the number length of the array:\n";
  cin >> N;
  cout <<"\nInput r, the number of integers 1-r:\n";
  cin >> R;

  if(N>50 || R>50)
    {
      cout << "Put in numbers smaller than 50.\n";
      return 1;
    }

  cout <<"\nN:"<<N<<"\tR:"<<R;
 
  for(i=0;i<R;i++)
    ARR[i]=0;
  ARR[0]=1;
  
  cout<<"\n";
  for(i=0;i<R;i++)
	cout<<ARR[i]<<"\t";

  for (i=1;i<N;i++)
    {
      incArray();
      cout<<"\n";
      for(j=0;j<R;j++)
	cout<<ARR[j]<<"\t";
      sum=0;
      for(j=0;j<R;j++)
	sum+=ARR[j];
      cout <<"CIRCLES:"<<(sum-(ARR[1]+ARR[R-1]))*R;
    }
  //We over counted the last increment so zero out states that end with 1,R-1
  ARR[1]=0;
  ARR[R-1]=0;
  cout<<"\n";
  for(j=0;j<R;j++)
    {
      if((j==1) || (j==(R-1)))
	cout<<"_\t";
      else
	cout<<" \t";
    }

  sum=0;
  for(i=0;i<R;i++)
    sum+=ARR[i];
  cout <<"\nSUM:"<<sum<<"\n";
  return 0;
}