AtCoder Beginner Contest 180
問題文
省略
省略
C++に変換後のコードはこちら
int N, M, L;
Modint dp[301][301], pre1[301][301], pre2[301][301];
Comb<Modint> c;
Modint solve(int L){
if(L==0) return 0;
rep(i,N+1) rep(j,M+1) dp[i][j] = 0;
dp[0][0] = 1;
rep(i,N+1) rep(k,1,L+1) pre1[i][k] = c.C(N-i-1, k-1) * c.fac(k) / 2;
rep(i,N+1) rep(k,1,L+1) pre2[i][k] = c.C(N-i-1, k-1) * c.fac(k-1) / 2;
rep(i,N+1) rep(j,M+1) if(dp[i][j] != 0){
rep(k,1,L+1){
if(i+k > N) break;
if(k==1){
if(i+k <= N && j+k-1 <= M) dp[i+k][j+k-1] += dp[i][j];
} else if(k==2){
if(i+k <= N && j+k-1 <= M) dp[i+k][j+k-1] += dp[i][j] * (N-i-1);
if(i+k <= N && j+k <= M) dp[i+k][j+k] += dp[i][j] * (N-i-1);
} else {
if(i+k <= N && j+k-1 <= M) dp[i+k][j+k-1] += dp[i][j] * pre1[i][k];
if(i+k <= N && j+k <= M) dp[i+k][j+k] += dp[i][j] * pre2[i][k];
}
}
}
return dp[N][M];
}
{
Modint res;
rd(N,M,L);
res += solve(L);
res -= solve(L-1);
wt(res);
}
Current time: 2024年04月18日19時05分29秒
Last modified: 2020年10月18日15時13分41秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Beginner_Contest ABC180 ABC_F
トップページに戻る
Logged in as: unknown user (not login)