작은 비숍(Little Bishops) - Programming Challenges
#include<stdio.h>
#define NUMBERLENGTH 5
#define ONEDIGIT 10000
typedef struct _longlong{
unsigned int h[NUMBERLENGTH];
} longlong;
static int n , k;
static longlong sol;
static longlong st;
static longlong s1,s2,s3,s4;
static int bk[17];
static int selected[17];
static int mm[17], dap[8][64];
void assign(longlong *a, unsigned int b)
{
int i;
for(i=0; i < NUMBERLENGTH; i++)
{
a->h[i] = b % ONEDIGIT;
b /= ONEDIGIT;
}
}
void add(longlong *c, const longlong *a, const longlong *b)
{
int i , carry;
carry = 0;
for(i=0;i < NUMBERLENGTH; i++)
{
c->h[i] = a->h[i] + b->h[i] + carry;
carry = c->h[i]/ONEDIGIT;
c->h[i] %= ONEDIGIT;
}
}
void sub(longlong *c, const longlong *a, const longlong *b)
{
int i, carry;
carry =0;
for(i=0; i < NUMBERLENGTH; i++)
{
if(a->h[i] >= b->h[i])
{
c->h[i] = a->h[i] - b->h[i] + carry;
carry = 0;
}
else
{
c->h[i] = (ONEDIGIT + a->h[i]) - b->h[i] + carry;
carry = -1;
}
}
}
void mul(longlong *c, const longlong *a, const longlong *b)
{
int i , j, carry;
unsigned int temp;
int in, jn;
longlong d;
for(i=0; i < NUMBERLENGTH; i++)
d.h[i] = 0;
in = jn = NUMBERLENGTH -1;
while(a->h[in] ==0)
in--;
in++;
while(b->h[jn] == 0)
jn--;
jn++;
for(i=0;i < in+1; i++)
{
carry =0;
for(j=0; j < jn+1; j++)
if(i+j < NUMBERLENGTH)
{
temp = (d.h[i+j] + a->h[i] * b->h[j] + carry) % ONEDIGIT;
carry = (d.h[i+j] + a->h[i]* b->h[j] + carry) / ONEDIGIT;
d.h[i+j] = temp;
}
}
for(i=0; i < NUMBERLENGTH; i++)
{
c->h[i] = d.h[i];
}
}
void print(const longlong *a)
{
int sw;
int i;
sw = 0;
for(i = NUMBERLENGTH - 1; i >=0; i--)
{
if(!(sw ==0 && a->h[i] == 0))
{
if(sw ==0)
{
printf("%d", a->h[i]);
sw =1;
}
else
printf("%04d", a->h[i]);
}
}
if(sw ==0)
printf("0");
}
void back(int a, int b)
{
int i , j, l;
if(a == -1 && b == -1)
{
j =0;
for(i=0; i < n*2 - 1; i++)
if(bk[i] == 1)
{
selected[j] = i;
if(i < n)
mm[j] = i+1;
else
mm[j] = n*2 - i -1;
j++;
}
i = 0;
j = k - 1;
while(i <=j)
{
if((n-1) - selected[i] > selected[j] - (n-1))
{
for( l = i +1; l <=j; l++)
{
if(selected[i] %2 == selected[l] %2)
mm[l]--;
}
i++;
}
else
{
for(l=i; l < j; l++)
if(selected[j] %2 == selected[l]%2)
mm[l]--;
j--;
}
}
assign(&s3, 1);
for(i=0;i <k; i++)
{
assign(&s1, mm[i]);
mul(&s2, &s1, &s3);
s3 = s2;
}
add(&s4, &sol, &s3);
sol = s4;
}
else
{
if(a >b)
{
bk[a] = 0;
back(a-1, b);
}
bk[a] = 1;
if(b >=0)
back(a - 1, b -1);
}
}
void main()
{
int t = 0;
for(n =1; n <= 8; n++)
{
for(k = 1; k <=64; k++)
{
assign(&sol, 0);
if( k < n*2 -1)
back(n*2 -2, k-1);
else
assign(&sol, 0);
dap[n-1][k-1] = (int) sol.h[1] * ONEDIGIT + (int)sol.h[0];
}
}
while(scanf("%d %d", &n, &k), n!=0 || k !=0)
{
if(k==0)
printf("1\n");
else if(n == 1 && k ==1)
printf("1\n");
else
printf("%ld\n", dap[n-1][k-1]);
}
}