D - Number of Multisets 题解(思维dp)

题目链接

题目大意

给你一个数k和n，表示用n个\(1/2^i(i=0,1,2.....)\)组成k有多少种方案数

题目思路

这个dp实属巧妙

设\(dp[i][j]表示i个数构成j\)

这i个数可以分为两种第一种为有1，第二种为无1

有一则可以直接从\(dp[i-1][j-1]\)转移

无一则可以从\(dp[i][2*j]\)让这i个数全部除以二即可

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF=0x3f3f3f3f3f3f3f3f;

const int maxn=3e3+5,mod=998244353;

int n,k;

ll dp[maxn][maxn];

int main(){

    scanf("%d%d",&n,&k);

    dp[0][0]=1;

    // dp[i][j] 表示i个数凑成k

    for(int i=1;i<=n;i++){

        for(int j=i;j>=1;j--){

            dp[i][j]=(dp[i-1][j-1]+(2*j<=i?dp[i][2*j]:0))%mod;

            // i个数内有1和无1

        }

    }

    printf("%lld\n",dp[n][k]);

    return 0;

}

巴特西

D - Number of Multisets 题解(思维dp)

题目链接

题目大意

题目思路

代码

最新文章

热门文章