fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
  3. #define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
  4. #define REP(i, n) for (int i = 0, _n = (n); i < _n; i++)
  5. #define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
  6. #define ALL(v) (v).begin(), (v).end()
  7. #define IS_INF(x)   (std::isinf(x))
  8. #define IS_NAN(x)   (std::isnan(x))
  9. #define fi   first
  10. #define se   second
  11. #define MASK(i) (1LL << (i))
  12. #define BIT(x, i) (((x) >> (i)) & 1)
  13. #define div   ___div
  14. #define next   ___next
  15. #define prev   ___prev
  16. #define left   ___left
  17. #define right   ___right
  18. #define __builtin_popcount __builtin_popcountll
  19. using namespace std;
  20. template<class X, class Y>
  21.     bool minimize(X &x, const Y &y) {
  22.         X eps = 1e-9;
  23.         if (x > y + eps) {
  24.             x = y;
  25.             return true;
  26.         } else return false;
  27.     }
  28. template<class X, class Y>
  29.     bool maximize(X &x, const Y &y) {
  30.         X eps = 1e-9;
  31.         if (x + eps < y) {
  32.             x = y;
  33.             return true;
  34.         } else return false;
  35.     }
  36. template<class T>
  37.     T Abs(const T &x) {
  38.         return (x < 0 ? -x : x);
  39.     }
  40.  
  41. /* Author: Van Hanh Pham */
  42.  
  43. /** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/
  44.  
  45. const int INF = (int)1e9 + 7;
  46. const int MOD = (int)1e9 + 7;
  47. void add(int &x, const int &y) {
  48.     x += y;
  49.     if (x >= MOD) x -= MOD;
  50. }
  51.  
  52. #define MAX_GROUP   111
  53. struct Node {
  54.     Node *child[26];
  55.     bool hasWord;
  56.     int numWord;
  57.     pair<int, int> dp[MAX_GROUP];
  58.  
  59.     Node() {
  60.         REP(i, 26) child[i] = NULL;
  61.         hasWord = false;
  62.         numWord = 0;
  63.     }
  64. };
  65.  
  66. Node *root;
  67. int numWord, numGroup;
  68. int comb[MAX_GROUP][MAX_GROUP], frac[MAX_GROUP];
  69.  
  70. void init(void) {
  71.     cin >> numWord >> numGroup;
  72.  
  73.     root = new Node();
  74.     REP(love, numWord) {
  75.         string word; cin >> word;
  76.         Node *p = root;
  77.         FORE(it, word) {
  78.             Node *&child = p->child[*it - 'A'];
  79.             if (child == NULL) child = new Node();
  80.             p = child;
  81.         }
  82.         p->hasWord = true;
  83.         p->numWord = 1;
  84.     }
  85.  
  86.     FOR(i, 1, numGroup) {
  87.         comb[i][0] = 0;
  88.         comb[0][i] = 1;
  89.     }
  90.     comb[0][0] = 1;
  91.     FOR(i, 1, numGroup) FOR(j, 1, numGroup) {
  92.         if (i > j) comb[i][j] = 0;
  93.         if (i == j) comb[i][j] = 1;
  94.         if (i < j) comb[i][j] = (comb[i][j - 1] + comb[i - 1][j - 1]) % MOD;
  95.     }
  96.     frac[0] = 1;
  97.     FOR(i, 1, numGroup) frac[i] = 1LL * frac[i - 1] * i % MOD;
  98. }
  99.  
  100. void update(pair<int, int> &cur, const pair<int, int> &tmp) {
  101.     if (maximize(cur.fi, tmp.fi)) cur.se = tmp.se;
  102.     else if (cur.fi == tmp.fi) add(cur.se, tmp.se);
  103. }
  104.  
  105. int countMerge(int x, int y, int z) {
  106.     int t = x + y - z;
  107.     return 1LL * comb[t][x] * comb[t][y] % MOD * frac[t] % MOD;
  108. }
  109.  
  110. pair<int, int> best[MAX_GROUP], prevBest[MAX_GROUP];
  111. void dfs(Node *p) {
  112.     REP(i, 26) if (p->child[i] != NULL) dfs(p->child[i]);
  113.  
  114.     REP(i, numGroup + 1) best[i] = {-INF, 0};
  115.  
  116.     if (p->hasWord) best[1] = {0, 1};
  117.     else best[0] = {0, 1};
  118.  
  119.     REP(i, 26) if (p->child[i] != NULL) {
  120.         Node *ch = p->child[i];
  121.  
  122.         REP(j, min(p->numWord, numGroup) + 1) {
  123.             prevBest[j] = best[j];
  124.             best[j] = {-INF, 0};
  125.         }
  126.  
  127.         REP(x, min(p->numWord, numGroup) + 1) REP(y, min(ch->numWord, numGroup) + 1)
  128.             FOR(z, max(x, y), min(x + y, numGroup)) {
  129.                 int numNode = prevBest[x].fi + ch->dp[y].fi;
  130.                 int numWay = 1LL * prevBest[x].se * ch->dp[y].se % MOD * countMerge(x, y, z) % MOD;
  131.                 update(best[z], {numNode, numWay});
  132.             }
  133.         p->numWord += ch->numWord;
  134.     }
  135.  
  136.     FOR(i, 1, numGroup) p->dp[i] = i <= p->numWord ? make_pair(best[i].fi + i, best[i].se) : make_pair(-INF, 0);
  137. }
  138.  
  139. void process(void) {
  140.     dfs(root);
  141.     cout << root->dp[numGroup].fi << " " << 1LL * root->dp[numGroup].se * frac[numGroup] % MOD << endl;
  142. }
  143.  
  144. int main(void) {
  145. #ifdef ONLINE_JUDGE
  146.     freopen("trie.inp", "r", stdin);
  147.     freopen("trie.out", "w", stdout);
  148. #endif // ONLINE_JUDGE
  149.     init();
  150.     process();
  151.     return 0;
  152. }
  153.  
  154. /*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/
  155.  
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/EwHSOF
Solution to problem "Trie sharding" - problem D from Google Code Jam 2014 round 2
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!