题目链接

【题意】

给出n和k（n<=64,k<=100）问你有多少个n位（无前导0）的二进制数的1和0一样多，同时值为k的倍数

【思路】

数位DP，dp[pos][sum][mod]dp[pos][sum][mod] 表示枚举到pos位时数字0和1的相对个数以及当前对应的数字modkmodk 对应的结果，记忆化搜索

#include
    
     using namespace std;typedef long long ll;int n,k;int a[80];ll dp[80][160][120];ll dfs(int pos,int sum,int mod,bool lead,bool limit){    if(pos==-1){        if(sum==80 && mod==0) return 1;        else return 0;    }    if(!lead && !limit && dp[pos][sum][mod]!=-1) return dp[pos][sum][mod];    int up=limit?a[pos]:1;    ll ans=0;    for(int i=0;i<=up;++i){        if(lead && i==0){            ans+=dfs(pos-1,sum,(mod*2+i)%k,lead,limit && i==up);        }        else{            ans+=dfs(pos-1,sum+(i==0?1:-1),(mod*2+i)%k,lead && 0==i,limit && i==up);        }    }    if(!lead && !limit) dp[pos][sum][mod]=ans;    return ans;}int main(){    //freopen("in.txt","r",stdin);    //freopen("out2.txt","w",stdout);    int T;    scanf("%d",&T);    for(int kase=1;kase<=T;++kase){        scanf("%lld%lld",&n,&k);        if(0==k){
   printf("Case %d: 0\n",kase);continue;}        memset(dp,-1,sizeof(dp));        for(int i=0;i