本来是数学排列组合的问题,但是求组合的算法没有涉猎过,只能动态规划过了,这题和背包问题一样。
dp[i][j]代表[0-i]的牌能拿到j分的组合数。dp[i][j]=dp[i-1][j]*2+dp[i-1][j-1].
C++ 代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
int arr[2001]={0};
int main(){
int n,s;
cin>>n>>s;
ll ans=0;
for (int i=0;i<n;++i) cin>>arr[i];
vector<vector<ll>> dp(n,vector<ll>(n,0));
dp[0][0]=2;
dp[0][1]=1;
for (int i=1;i<n;++i){
for (int j=0;j<=min(s,i+1);++j){
dp[i][j]=(dp[i-1][j]*2+(j-1>=0? dp[i-1][j-1]:0))%mod;
}
}
cout<<dp[n-1][s]<<endl;
}