提出 #18170654

---

ソースコード 拡げる

/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define m_k make_pair
#define mod 1000000007
#define int long long
using namespace std;
const int N=2100;
int n,k,dp[N][N],sum[N];
inline void add(int &a,int b){a=((a+b>mod)?a+b-mod:a+b);}
inline void del(int &a,int b){a=((a-b<0)?a-b+mod:a-b);}
inline void mul(int &a,int b){a=(a*b)%mod;}
inline int m_pow(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) mul(ans,a);
		b>>=1;
		mul(a,a);
	}
	return ans;
}
inline int read()
{
	int f=1,x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	return x*f;
}
signed main()
{
	n=read();k=read();
	if (n==1)
	{
		printf("1\n");
		return 0;
	}
	if (k==1)
	{
		printf("%lld\n",m_pow(2,n-2));
		return 0;
	}
	dp[0][n+1]=1;
	for (int i=1;i<=n+1;i++) sum[i]=1;
	for (int i=1;i<k;i++)
	{
		for (int j=1;j<=n-i+1;j++)
		{
			dp[i][j]=sum[j+1];
			add(dp[i][j],dp[i-1][j]);
		}
		for (int j=1;j<=n+1;j++) sum[j]=0;
		for (int j=n-i+1;j>=1;j--) sum[j]=(sum[j+1]+dp[i][j])%mod;
	}
	int ans=sum[2];
	if (k!=n) mul(ans,m_pow(2,n-k-1));
	printf("%lld\n",ans);
}

提出情報

ジャッジ結果