SRM440 Div2 Hard

1000

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

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;
  }
};