結果
問題 | No.563 超高速一人かるた large |
ユーザー | yukudo |
提出日時 | 2017-08-25 23:44:41 |
言語 | C++11 (gcc 11.4.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,642 bytes |
コンパイル時間 | 1,554 ms |
コンパイル使用メモリ | 161,516 KB |
実行使用メモリ | 11,852 KB |
最終ジャッジ日時 | 2024-10-15 16:16:05 |
合計ジャッジ時間 | 4,740 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 5 ms
11,604 KB |
testcase_01 | AC | 4 ms
11,520 KB |
testcase_02 | AC | 6 ms
11,648 KB |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | AC | 9 ms
11,852 KB |
testcase_20 | RE | - |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";} template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;} template<class T>bool chmin(T&a,const T&b){return a>b?(a=b,1):0;} template<class T>bool chmax(T&a,const T&b){return a<b?(a=b,1):0;} const ll MOD = 1000000007; const int MAX_N = 20; string s[MAX_N]; int diff[MAX_N][MAX_N]; ll dp[1 << MAX_N]; ll fact[MAX_N + 10]; int main2() { int N; cin >> N; fact[0] = 1; for (int i = 1; i <= N; i++) fact[i] = (fact[i-1] * i) % MOD; REP(i, N) { cin >> s[i]; s[i] += "$"; } REP(i, N) REP(j, N) { int d = 0; if (i == j) d = 1; else { while (s[i][d] == s[j][d]) d++; d++; } diff[i][j] = d; } memset(dp, 0, sizeof(dp)); for (int s = 0; s < (1 << N); s++) { int on = __builtin_popcount(s); REP(k, N) if ((s >> k & 1) == 0) { int cost = 0; REP(j, N) if ((s >> j & 1) == 0) { chmax(cost, diff[k][j]); } // if (N == 3) { // cout << bitset<3>(s) << " " << dp[s] << " k=" << k << " " << cost << endl; // } (dp[s | (1 << k)] += dp[s] + cost * fact[on]) %= MOD; } } vector<ll> ans(N+1); for (int s = 0; s < (1 << N); s++) { (ans[__builtin_popcount(s)] += dp[s]) %= MOD; } for (int i = 1; i <= N; i++) { cout << ans[i] << endl; } return 0; } int main() { for (;!cin.eof();cin>>ws) main2(); return 0; }