SRM440 Div2 Hard

1000

dp[ どれを使ったか ][ これまでの余り ]

view plainprint?

1. int divS(string s, int K)  
2. {  
3.   vector<int> v;  
4.   for (int i = 0; i < s.size(); ++i) {  
5.     v.push_back(s[i] - '0');  
6.   }  
7.   for (int i = 0; i + 1 < v.size(); ++i) {  
8.     v[i + 1] += (v[i] % K) * 10;  
9.   }  
10.   return v.back() % K;  
11. }  
12.   
13. lli gcd(lli a, lli b)  
14. {  
15.   return b ? gcd(b, a % b) : a;  
16. }  
17.   
18. class WickedTeacher {  
19. public:  
20.   string cheatProbability(vector <string> ns, int K)  
21.   {  
22.     const int N = 15 + 1;  
23.     const int BIT = 1 << N;  
24.     const int M = 101;  
25.   
26.     char buff[1000];  
27.     int D[N][M];  
28.     for (int i = 0; i < ns.size(); ++i) {  
29.       for (int j = 0; j < K; ++j) {  
30.         sprintf(buff, "%d", j);  
31.         string t = string(buff) + ns[i];  
32.         D[i][j] = divS(t, K);  
33.       }  
34.     }  
35.   
36.     static lli dp[BIT][M];  
37.     fill(&dp[0][0], &dp[BIT][0], 0);  
38.     dp[0][0]= 1;  
39.   
40.     for (int bit = 0; bit < (1 << ns.size()); ++bit) {  
41.       for (int m = 0; m < M; ++m) {  
42.         if (dp[bit][m] == 0) continue;  
43.         for (int i = 0; i < ns.size(); ++i) {  
44.           if (bit & (1 << i)) continue;  
45.           dp[bit | (1 << i)][D[i][m]] += dp[bit][m];  
46.         }  
47.       }  
48.     }  
49.   
50.     lli q = 0;  
51.     lli p = dp[(1 << ns.size()) - 1][0];  
52.   
53.     for (int m = 0; m < K; ++m) {  
54.       q += dp[(1 << ns.size()) - 1][m];  
55.     }  
56.     if (p == 0 && q == 0) return "0/0";  
57.   
58.     lli r = gcd(max(p, q), min(p, q));  
59.     p /= r;  
60.     q /= r;  
61.   
62.     string P, Q;  
63.     sprintf(buff, "%lld", p);  
64.     P = string(buff);  
65.     sprintf(buff, "%lld", q);  
66.     Q = string(buff);  
67.     return P + "/" + Q;  
68.   }  
69. };  

int divS(string s, int K)
{
  vector<int> v;
  for (int i = 0; i < s.size(); ++i) {
    v.push_back(s[i] - '0');
  }
  for (int i = 0; i + 1 < v.size(); ++i) {
    v[i + 1] += (v[i] % K) * 10;
  }
  return v.back() % K;
}

lli gcd(lli a, lli b)
{
  return b ? gcd(b, a % b) : a;
}

class WickedTeacher {
public:
  string cheatProbability(vector <string> ns, int K)
  {
    const int N = 15 + 1;
    const int BIT = 1 << N;
    const int M = 101;

    char buff[1000];
    int D[N][M];
    for (int i = 0; i < ns.size(); ++i) {
      for (int j = 0; j < K; ++j) {
        sprintf(buff, "%d", j);
        string t = string(buff) + ns[i];
        D[i][j] = divS(t, K);
      }
    }

    static lli dp[BIT][M];
    fill(&dp[0][0], &dp[BIT][0], 0);
    dp[0][0]= 1;

    for (int bit = 0; bit < (1 << ns.size()); ++bit) {
      for (int m = 0; m < M; ++m) {
        if (dp[bit][m] == 0) continue;
        for (int i = 0; i < ns.size(); ++i) {
          if (bit & (1 << i)) continue;
          dp[bit | (1 << i)][D[i][m]] += dp[bit][m];
        }
      }
    }

    lli q = 0;
    lli p = dp[(1 << ns.size()) - 1][0];

    for (int m = 0; m < K; ++m) {
      q += dp[(1 << ns.size()) - 1][m];
    }
    if (p == 0 && q == 0) return "0/0";

    lli r = gcd(max(p, q), min(p, q));
    p /= r;
    q /= r;

    string P, Q;
    sprintf(buff, "%lld", p);
    P = string(buff);
    sprintf(buff, "%lld", q);
    Q = string(buff);
    return P + "/" + Q;
  }
};