結果
問題 | No.1513 simple 門松列 problem |
ユーザー |
![]() |
提出日時 | 2021-05-21 23:11:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 658 ms / 3,000 ms |
コード長 | 1,916 bytes |
コンパイル時間 | 1,741 ms |
コンパイル使用メモリ | 169,748 KB |
実行使用メモリ | 255,908 KB |
最終ジャッジ日時 | 2024-10-10 10:05:52 |
合計ジャッジ時間 | 5,917 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ll long long #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define Pr pair<ll,ll> #define Tp tuple<ll,ll,ll> using Graph = vector<vector<Pr>>; ll mod = 998244353; int main() { ll N,K; cin >> N >> K; ll ans = 0; ll ans2 = 0; ll dp[N+1][K][K],sum[N+1][K+1][K+1]; ll dp2[N+1][K][K],sum2[N+1][K+1][K+1]; rep(i,N+1){ rep(j,K){ rep(k,K){ dp[i][j][k] = 0; dp2[i][j][k] = 0; } } } rep(i,N+1){ rep(j,K+1){ rep(k,K+1){ sum[i][j][k] = 0; sum2[i][j][k] = 0; } } } rep(i,K){ rep(j,K){ if(i!=j){ dp[2][i][j] = 1; dp2[2][i][j] = i+j; } } } for(int i=3;i<=N;i++){ rep(j,K){ rep(k,K){ sum[i-1][k+1][j] = (sum[i-1][k][j]+dp[i-1][k][j])%mod; sum2[i-1][k+1][j] = (sum2[i-1][k][j]+dp2[i-1][k][j])%mod; } } rep(j,K){ rep(k,K){ if(j<k){ dp[i][j][k] = (sum[i-1][K][j]-sum[i-1][j+1][j]-dp[i-1][k][j]+2*mod)%mod; dp2[i][j][k] = (sum2[i-1][K][j]-sum2[i-1][j+1][j]-dp2[i-1][k][j]+2*mod)%mod; dp2[i][j][k] += (dp[i][j][k]*k)%mod; dp2[i][j][k] %= mod; } else if(j>k){ dp[i][j][k] = (sum[i-1][j][j]-dp[i-1][k][j]+2*mod)%mod; dp2[i][j][k] = (sum2[i-1][j][j]-dp2[i-1][k][j]+2*mod)%mod; dp2[i][j][k] += (dp[i][j][k]*k)%mod; dp2[i][j][k] %= mod; } } } } rep(i,K){ rep(j,K){ ans += dp[N][i][j]; ans %= mod; ans2 += dp2[N][i][j]; ans2 %= mod; } } cout << ans << " " << ans2 << endl; }