結果
問題 |
No.562 超高速一人かるた small
|
ユーザー |
![]() |
提出日時 | 2017-08-25 23:19:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,625 bytes |
コンパイル時間 | 1,319 ms |
コンパイル使用メモリ | 110,516 KB |
実行使用メモリ | 172,288 KB |
最終ジャッジ日時 | 2024-10-15 16:43:22 |
合計ジャッジ時間 | 7,323 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 -- * 1 |
other | AC * 7 TLE * 1 -- * 13 |
ソースコード
#include<iostream> #include<iomanip> #include<math.h> #include<vector> #include<algorithm> #include<set> #include<map> #include<queue> #include<stack> #include<string> #include<complex> #include<random> #include<time.h> #define INF 1000000000ll #define MOD 1000000007ll #define EPS 1e-8 #define REP(i, m) for(long long i = 0; i < m; ++i) #define FOR(i, n, m) for(long long i = n; i < m; ++i) #define ALL(v) v.begin(), v.end() #define pb push_back using namespace std; typedef long long ll; typedef pair<ll, ll> P; typedef long double ld; ll fact(ll a) { if(a==0) return 1; else return (a*fact(a-1))%MOD; } int main() { ios::sync_with_stdio(false); int n; cin>>n; vector<string> s(n); REP(i,n) cin>>s[i]; vector<ll> res(n,0); ll dp[n][1<<n]; REP(i,n) { REP(j,1<<n) dp[i][j]=0; } REP(j,1<<n) { REP(i,n) { vector<ll> p; vector<ll> q; ll buf=j; REP(k,n) { if(buf%2==1) p.pb(k); else q.pb(k); buf/=2; } bool d=false; REP(k,p.size()) { if(p[k]==i) d=true; } if(!d) continue; ll foo=0; REP(k,s[i].size()) { ++foo; bool f=false; REP(l,q.size()) { if(k<s[q[l]].size()&&s[q[l]][k]==s[i][k]) f=true; } if(!f) break; if(k==s[i].size()-1) ++foo; } foo*=fact(p.size()-1); if(p.size()==1) dp[i][j]=foo%MOD; else { REP(k,p.size()) { if(p[k]==i) continue; foo+=dp[p[k]][j^(1<<i)]; foo%=MOD; } dp[i][j]=foo; } } } REP(i,n) { REP(j,1<<n) { ll buf=j; int c=0;; REP(k,n) { if(buf%2==1) ++c; buf/=2; } res[c-1]+=dp[i][j]; res[c-1]%=MOD; } } REP(i,n) cout<<res[i]<<endl; }