- 数学
AT_arc068_d [ARC068D] Solitaire代码
- 2022-10-19 18:03:20 @
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=2001;
int dp[N][N],n,k;//dp ij 取了i个,最小值j
int qpow(int a,int b)
{
int ans=1,base=a;
while(b)
{
if(b&1)
{
ans*=base;
ans%=mod;
}
base*=base;
base%=mod;
b>>=1;
}
return ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin>>n>>k;
if(n==1)
{
cout<<1;
return 0;
}
for(int i=2;i<=n;i++)
{
dp[1][i]=1;
}
for(int i=1;i<k-1;i++)
{
dp[i+1][n-i+1]=dp[i][n-i+1];
for(int j=n-i;j>1;j--)
{
dp[i+1][j]=(dp[i+1][j+1]+dp[i][j])%mod;
}
}
int ans=0;
for(int i=1;i<=n-k+2;i++)
{
ans+=dp[k-1][i];
ans%=mod;
}
cout<<ans*qpow(2,n-k-1)%mod;
return 0;
}
0 条评论
目前还没有评论...