Source Code

Problem: 3556		User: test_3556
Memory: 40500K		Time: 954MS
Language: C++		Result: Accepted
Source Code
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<stdio.h>
using namespace std; 
int vl[9366825],list[1000000],cnt_list;
bool vis[9366825];
int c[48][48],wss[48][48][7],ax; 
int n,b,mod=1000000000;
int dfs(int num[],int state)
{
	int i,j;
    if(num[b]==0)
        return 1; 
	if(vis[state])
       return vl[state];
    list[cnt_list++]=state;
    int nstate=state;
    int tmp[6];
    for(i=0;i<=b;i++)
       tmp[i]=num[i];
	vis[state]=true;
	vl[state]=0;
	long long ret=0;
	for(i=b;i>0;i--)
	{
		if(num[i]<=0)
		    break;
	     tmp[i]--;
		nstate-=c[tmp[i]+i+1][i];
		for(j=num[i];j>num[i-1];j--)
		{
		    if(i==1)
		       j=1;
			nstate-=wss[tmp[i-1]][j-1][i];
			tmp[i-1]=j-1;
			if(vis[nstate])
			   ret+=vl[nstate];
            else
               ret+=dfs(tmp,nstate);
		}
	} 
	vl[state]=ret%mod;
	return vl[state];
}
int f()
{
	int i,j,res,state=0;
	int num[6]={0},big=0;
	num[b]=n;
	for(i=0;i<=b;i++)
	   state+=c[num[i]+i+1][i+1];
    cnt_list=0;
    res=dfs(num,state); 
    for(i=0;i<cnt_list;i++)
        vis[list[i]]=false;
    return res; 
}
int main()
{
	int v[6],i,j,s,p,q,k,num_st=0;
    for(i=0;i<=47;i++) 
      for(j=0;j<=6;j++)
      {
      	  if(j==0||j==i)
      	     c[i][j]=1;
   	      else
   	         c[i][j]=c[i-1][j-1]+c[i-1][j];
      }
    	for(i=0;i<=40;i++)
	   for(j=0;j<=40;j++)
	      for(s=0;s<=6;s++)
      		   wss[i][j][s]=c[i+s][s]-c[j+s][s];
    scanf("%d%d",&n,&b);
	 int ans=f();;
     b--; 
	 ans=(ans-f()+mod)%mod;
     b++;
     printf("%d\n",ans);
	return 0;
}