結果
問題 | No.287 場合の数 |
ユーザー |
![]() |
提出日時 | 2023-10-21 04:04:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 2,023 bytes |
コンパイル時間 | 907 ms |
コンパイル使用メモリ | 118,900 KB |
最終ジャッジ日時 | 2025-02-17 12:17:25 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 22 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>#include<cstring>#include<cassert>#include<cmath>#include<ctime>#include<iomanip>#include<numeric>#include<stack>#include<queue>#include<map>#include<unordered_map>#include<set>#include<unordered_set>#include<bitset>#include<random>using namespace std;int N;long long dp[2][601];//int fc[9];void solve(){cin >> N;int cur = 0,M = 6*N;dp[cur][0] = 1;for(int i = 0;i < 8;i++){int nxt = 1-cur;for(int j = 0;j <= M;j++) dp[nxt][j] = 0;for(int j = 0;j <= M;j++)for(int k = 0;k <= N && k+j <= M;k++) dp[nxt][j+k] += dp[cur][j];swap(cur,nxt);}cout << dp[cur][M] << endl;/*cin >> N;fc[0] = 1;for(int i = 1;i <= 8;i++) fc[i] = fc[i-1]*i;vector<pair<int,long long>> A;auto f = [&](int i,int j,int k,int l) -> int{return i + (long long)j*(N+1) + (long long)k*(N+1)*(N+1) + (long long)l*(N+1)*(N+1)*(N+1);};for(int i = 0;i <= N;i++)for(int j = i;j <= N;j++)for(int k = j;k <= N;k++)for(int l = k;l <= N;l++){A.push_back(make_pair(i+j+k+l,f(i,j,k,l)));}sort(A.begin(),A.end());long long ans = 0;int M = 6*N,K = (int)A.size();vector<pair<int,long long>> B(A.rbegin(),A.rend());unordered_set<long long> S;auto g = [&](long long l,long long r) -> int{vector<int> v(8);for(int i = 0;i < 4;i++) v[i] = l%(N+1),l /= N+1;for(int i = 0;i < 4;i++) v[i+4] = r%(N+1),r /= N+1;sort(v.begin(),v.end());long long H = 0;for(int i = 0;i < 8;i++) H = H*(N+1) + v[i];if(S.count(H)) return 0;S.insert(H);v.push_back(101);int res = fc[8];int cur = 1;for(int i = 1;i <= 8;i++){if(v[i-1] == v[i]) cur++;else res /= fc[cur],cur = 1;}return res;};int bi = 0;for(int i = 0;i < K;i++){while(bi < K && A[i].first+B[bi].first > M) bi++;if(bi < K && A[i].first+B[bi].first == M) ans += g(A[i].second,B[bi].second);}cout << ans << endl;*/}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;//cin >> tt;while(tt--) solve();}