C++11(clang++ 3.9) 解法, 执行用时: 38ms, 内存消耗: 436K, 提交时间: 2017-12-23 21:48:11

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stdio.h>
#include<algorithm>
#include<cmath>
using namespace std;
const int mod=1e9+7;
int n,m,rev[111],fac[111];
int dp[2][71][36][2];
int power(int a,int n)
{
	if(n==0)
	   return 1;
    int ret=power(a,n/2);
    ret=1LL*ret*ret%mod;
    if(n%2)
       ret=1LL*ret*a%mod;
    return ret;
}
int main()
{
	scanf("%d%d",&n,&m);
	int i,j,s,p,q,a[6],t,na[6];
	for(i=0;i<=n;i++)
    {
    	if(i==0)
    	   fac[i]=1;
 	    else
 	       fac[i]=1LL*fac[i-1]*i%mod;
        rev[i]=power(fac[i],mod-2);
    }
	int flag=0;
	memset(dp[flag],0,sizeof(dp[flag]));
	int su=0;
	dp[0][1][0][0]=1;
	for(a[0]=1;a[0]<=n/2;a[0]++)
	   for(a[1]=0;a[1]<=min(m,a[0]/2);a[1]++)
	      for(a[2]=0;a[2]<2;a[2]++)
	      {
      		   memset(dp[1-flag],0,sizeof(dp[1-flag]));
      		   for(a[3]=1;a[3]<=n;a[3]++)
				  for(a[4]=0;a[4]<=min(m,a[3]/2);a[4]++)
				     for(a[5]=0;a[5]<2;a[5]++)
					 {
					 	  if(dp[flag][a[3]][a[4]][a[5]]==0)
					 	      continue;
	 	                  int now=1,mv=dp[flag][a[0]][a[1]][a[2]]; 
						  for(t=0;a[3]+a[0]*t<=n&&a[4]+a[1]*t<=m;t++)
 						  {
 						  	  int da=0,tmp;
  						 	  if(a[5]==0&&a[2]==0&&t>0)
								  da=na[5]=1;
							  else
							      na[5]=a[5];
							  na[3]=a[3]+a[0]*t;
							  na[4]=a[4]+a[1]*t+da;
							  if(na[4]<=m)
							  {
							     tmp=1LL*dp[flag][a[3]][a[4]][a[5]]*now%mod*rev[t]%mod;
							     dp[1-flag][na[3]][na[4]][na[5]]=(dp[1-flag][na[3]][na[4]][na[5]]+tmp)%mod;
							  }
							  now=1LL*now*(mv+t)%mod; 
  						  }
 					 } 
			    flag^=1;
       	  } 
	int ans;
	ans=(dp[flag][n][m][0]+dp[flag][n][m][1])%mod;
	if(n%2==0)
    {
    	 int tmp=0,m1,m2;
    	 for(m1=0;m1<=m;m1++)
    	 {
 	    	 for(i=0;i<2;i++)
 	    	 	for(j=0;j<2;j++)
 	    	 	{
	 	    	 	s=0;
	 	    	 	if(i==0&&j==0)
	 	    	 	    s=1;
   	 	             m2=m-m1-s;
				     if(m2>=0)
					 {
 						tmp=(tmp+1LL*dp[flag][n/2][m1][i]*dp[flag][n/2][m2][j])%mod;
					    if(i==j&&m1==m2)
    						 tmp=(tmp-dp[flag][n/2][m1][i]+mod)%mod;
					 }
				 }
 	     }
 	     ans=ans-1LL*tmp*((mod+1)/2)%mod;
 	     if(ans<0)
 	        ans+=mod;
    }
    printf("%d\n",ans);
	return 0;
}
/*
2 1

*/