結果
問題 | No.140 みんなで旅行 |
ユーザー |
|
提出日時 | 2022-05-11 20:46:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,158 ms / 5,000 ms |
コード長 | 1,142 bytes |
コンパイル時間 | 4,081 ms |
コンパイル使用メモリ | 256,892 KB |
最終ジャッジ日時 | 2025-01-29 06:05:26 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h>using namespace std;#include<atcoder/all>using namespace atcoder;using ll = long long;using mint = modint1000000007;int n;//mint dp[556][556][556];void solve(){vector<vector<vector<mint>>> dp(556+1);dp[0] = vector<vector<mint>>(556+1,vector<mint>(556+1));dp[1] = vector<vector<mint>>(556+1,vector<mint>(556+1));dp[1][1][1] = 1;dp[1][2][0] = 1;for(int i = 1;i<n;i++){dp[i+1] = vector<vector<mint>>(556+1,vector<mint>(556+1));for(int j = 0;j<556-1;j++){for(int k = 0;k<556+1;k++){dp[i+1][j][k+1] += dp[i][j][k] *(j-k);dp[i+1][j][k] += dp[i][j][k] *k;dp[i+1][j][k] += dp[i][j][k] * j*(j-1);dp[i+1][j+1][k+1] += dp[i][j][k];dp[i+1][j+1][k] += dp[i][j][k]*j*2;dp[i+1][j+2][k] += dp[i][j][k];}}dp[i].clear();}mint ans = 0;for(int i = 0;i<=n;i++){//cerr<<i<<':'<<dp[n][i][i].val()<<endl;ans += dp[n][i][i];}/*for(int i = 0;i<10;i++){for(int j = 0;j<10;j++){cerr<<dp[2][i][j].val()<<' ';}cout<<endl;}*/cout<<ans.val()<<endl;}signed main(){cin.tie(nullptr);ios::sync_with_stdio(false);cin >> n;solve();}