1036.c

来自「平时acm训练时ac的源代码」· C语言 代码 · 共 131 行

// ural_1036.cpp : 定义控制台应用程序的入口点。
//

#include "stdio.h"
#define M 450
#define T 8
#define U 100000000
#define LEN 9

#define LEN_A 300
#define LEN_B 200

int main()
{
	unsigned long a[2][M+1][T];
	int h,i,j,k,t1,t2,e,f,up,down;
	int n,s;
	int ch1,ch2;
	int out[LEN_A];
	int r[LEN_B];

	while(1)
	{

	scanf("%d%d",&n,&s);
	if(s<0||(s%2==1&&s>0)) {printf("0"); goto z;}
	if(s>18*n) {  printf("0"); goto z;}
	if(s==0) {  printf("1"); goto z;}

	s/=2;

    for(i=0;i<10;i++)
	{
		a[0][i][0]=1;
		for(j=1;j<T;j++)
			a[0][i][j]=0;
	}

	ch2=0;
	for(i=2;i<=n;i++)
	{
		ch1=ch2;
		ch2^=1;
		up=i*9<s ? i*9:s;
		down=s-(n-i)*9;
		if(down<0) down=0;
		e=up<9 ? up:9;

		for(j=down;j<=e;j++)
		{
			for(k=0;k<T;k++)
			  a[ch2][j][k]=0;
			for(h=0;h<=j;h++)
			{
				for(k=0;k<T-1;k++)
				{
					a[ch2][j][k]+=a[ch1][j-h][k];
					a[ch2][j][k+1]+=a[ch2][j][k]/U;
					a[ch2][j][k]%=U;
				}
			}
		}
		f=10>down ?10 :down;
		for(j=f;j<=up;j++)
		{
			for(k=0;k<T;k++)
			  a[ch2][j][k]=0;
			t1=0;
			if(j>(i-1)*9) t1=j-(i-1)*9;
			t2=9<j ? 9:j;
			for(h=t1;h<=t2;h++)
			 {
               for(k=0;k<T-1;k++) 
			   {
				   a[ch2][j][k]+=a[ch1][j-h][k];
				   a[ch2][j][k+1]+=a[ch2][j][k]/U;
				   a[ch2][j][k]%=U;
			   }
			 }
		}
	}
	h=0;
	for(i=0;i<T;i++)
	{
		if(a[ch2][s][i]>0)
		{
			k=0;
		 while(a[ch2][s][i]>0)
		 {
			r[h]=a[ch2][s][i]%10;
			h++;k++;
			a[ch2][s][i]/=10;
		 }
		 for(k=k+1;k<LEN;k++)
		 {   r[h]=0;h++; }
		}
		else
	    	for(k=1;k<LEN;k++)
		    {  r[h]=0;h++; }
	}


	for(i=0;i<LEN_A;i++)
		out[i]=0;

	for(i=0;i<h;i++)
	{
		k=i;
		for(j=0;j<h;j++)
		{
			e=r[i]*r[j];
			out[k]+=e;
			out[k+1]+=out[k]/10;
			out[k]%=10;
			k++;
		}
	}

	k=LEN_A-1;
	while(out[k]==0&&k>0)
	  k--;

	for(i=k;i>=0;i--)
		printf("%d",out[i]);
z:	printf("\n");
	}
	return 0;
}