原文链接https://www.cnblogs.com/zhouzhendong/p/ARD102E.html
咕咕咕
明日再写……
扯淡还是要先撤的。比赛的时候被 D 题续了好久, E 题差一句话就调出来了。如果赛后与 Functionendless 交流完 D 题,回来检查这题,然后检查了 2 分钟就发现了错误…… QAQ
咕咕咕
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2005,mod=998244353;
LL read(){
LL x=0,f=1;
char ch=getchar();
while (!isdigit(ch)&&ch!=‘-‘)
ch=getchar();
if (ch==‘-‘)
f=-1,ch=getchar();
while (isdigit(ch))
x=(x<<1)+(x<<3)+ch-48,ch=getchar();
return x*f;
}
int Pow(int x,int y){
int ans=1;
for (;y;y>>=1,x=1LL*x*x%mod)
if (y&1)
ans=1LL*ans*x%mod;
return ans;
}
int n,k,dp[N][N],C[N][N],sum[N][N];
int DP(int i,int j){
if (j<0)
return 0;
return dp[i][j];
}
int Get(int v,int n,int k){
int ans=0;
int lim=max(0,v/2-max(0,v-k-1));
for (int i=0;i<=lim;i++)
ans=(1LL*Pow(2,i)*C[lim][i]%mod*DP(k-lim*2+i,n-i)+ans)%mod;
return ans;
}
int main(){
for (int i=0;i<N;i++)
C[i][0]=C[i][i]=1;
for (int i=1;i<N;i++)
for (int j=1;j<i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
k=read(),n=read();
dp[0][0]=sum[0][0]=1;
for (int i=1;i<=n;i++)
sum[0][i]=1;
for (int i=1;i<=k;i++){
dp[i][0]=sum[i][0]=1;
for (int j=1;j<=n;j++){
dp[i][j]=sum[i-1][j];
sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
}
}
for (int i=2;i<=2*k;i++){
int ans=0;
if (i&1)
ans=(ans+Get(i,n,k))%mod;
else
ans=(1LL*ans+Get(i-1,n,k-1)+Get(i-1,n-1,k-1))%mod;
printf("%d\n",ans);
}
return 0;
}
AtCoder Regular Contest (ARC102) E - Stop. Otherwise... 排列组合 动态规划
原文:https://www.cnblogs.com/zhouzhendong/p/ARD102E.html