传送门：Zeros and Ones
题意：求总数位为n包含0和1个数相同且整除k的二进制数的个数。
分析：设dp[pos][num][md]表示还有pos位已包含num个1且模k余md的符合条件的二进制数的个数，裸数位dp题。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#define LL long long
#define N 3000010
using namespace std;
int n,k;
LL dp[][][];
LL dfs(int pos,int num,int md,int fzore)
{
if(!pos)
{
return num==n/&&!md;
}
if(~dp[pos][num][md])return dp[pos][num][md];
LL ans=;
for(int i=;i<=;i++)
{
if(fzore)
{
if(i==)ans+=dfs(pos-,num+,(md*+i)%k,);
}
else
{
if(i==)ans+=dfs(pos-,num+,(md*+i)%k,);
else ans+=dfs(pos-,num,(md*+i)%k,);
}
}
dp[pos][num][md]=ans;
return ans;
}
int main()
{
int T,cas=; scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
printf("Case %d: ",cas++);
memset(dp,-,sizeof(dp));
if(k==||n%==)
{
puts("");continue;
}
printf("%lld\n",dfs(n,,,));
}
}