题意：给你n、k，问你有多少个n为二进制的数（无前导零）的0与1一样多，且是k的倍数
题解：对于每个k都计算一次dp，dp[i][j][kk][l]表示i位有j个1模k等于kk且第一位为l（0/1）
再次预处理mod[i][j]表示1的i次方模j等于几，具体看代码注释
import java.util.Scanner; public class Main{ static int Maxn=65; static int Maxk=101; //前i个数有j个1模给定的值余k且第一位为1或者0的总个数 static long[][][][] dp = new long[Maxn][Maxn][Maxk][2]; //初始化1的i次方模j等于几 static int[][] Mod=new int[Maxn][Maxk]; //初始化 static void Init(){ for(int i=0;i<Maxn;++i){ for(int j=1;j<Maxk;++j){ Mod[i][j]=(int) ((1L << i)%j); } } } //按位dp求出当有n位是模kk等于0的总个数 static long Solve(int n,int kk){ if(kk==0||(n&1)==1)//特判 return 0L;for(int i=0;i<=n;++i)//初始化 for(int j=0;j<=i;++j) for(int k=0;k<=kk;++k){ dp[i][j][k][0]=dp[i][j][k][1]=0L; } dp[0][0][0][0]=1L; //每种dp的i位只与i-1位相关 for(int i=1;i<=n;++i){ //求i位有i/2个1时需要i-1位有i/2与i/2-1个1，但是再向前推就需要更多所以将出现所有可能个1的情况求出 for(int j=0;j<=i&&j<=n/2;++j){ //模kk等于所有k的情况都需要求出，用于下一次使用 for(int k=0;k<kk;++k){ //此位置放0 dp[i][j][k][0]+=dp[i-1][j][k][0]+dp[i-1][j][k][1]; //此位置放1,k就等于前一个是当前位置减去（1<<i-1）后再模kk的值 if(j>0){ dp[i][j][k][1]+=dp[i-1][j-1][(k+kk-Mod[i-1][kk])%kk][0]+dp[i-1][j-1][(k+kk-Mod[i-1][kk])%kk][1];//计算余数 } } } } return dp[n][n/2][0][1]; } public static void main(String[] args) { int t,coun=0; int n,k; Init(); Scanner sc =new Scanner(System.in); t=sc.nextInt(); while(t!=0){ n=sc.nextInt(); k=sc.nextInt(); System.out.println("Case "+(++coun)+": "+Solve(n,k)); t--; } } }