</pre>以状态d(i,j,k)代表第前i位用j个一能组成所有对K取模余数为k的数状态转移即该位置为1还是0<p>还有一点要说明 最后结果不是d(n-1,n/2-1,K-yu[n] (yu[n]为2^(n-1)对K取模后的值) ) 而是d(n-1,n/2-1,（K-yu[n]）%K）;</p><p><pre name="code" class="html">#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 66;
const int maxk = 105;
long long d[maxn][maxn][maxk];
bool vis[maxn][maxn][maxk];
int yu[maxn],n,K;
long long dp(int i,int j,int k){
if(vis[i][j][k]) return d[i][j][k];
vis[i][j][k]=true;
if(i==0){
if(j!=0) return d[i][j][k]=0;
return d[i][j][k] = (k%K==0 ? 1 : 0);
}
d[i][j][k]=dp(i-1,j,k);
if(j>0) d[i][j][k]=d[i][j][k]+dp(i-1,j-1,(K+k-yu[i])%K);
return d[i][j][k];
}
int main()
{
int T;
scanf("%d",&T);
int kase=1;
while(T--){
scanf("%d %d",&n,&K);
printf("Case %d: ",kase++);
if(n&1||K==0) printf("0\n");
else{
yu[1]=1;
for(int i=2;i<=n;i++){
yu[i]=(yu[i-1]*2)%K;
}
memset(vis,false,sizeof(vis));
long long temp = dp(n-1,n/2-1,(K-yu[n])%K );
printf("%lld\n",temp);
}
}
}