久々の参加です。リハビリのために565の250を解いたら199ptsでした・・・。
class PenguinSledding { public: ll count2Plus(ll n) { return (1LL << n) - n - 1; } long long countDesigns(int numCheckpoints, vector <int> checkpoint1, vector <int> checkpoint2) { int N = numCheckpoints; vector<set<int> > g(N); REP(i, checkpoint1.size()) { int a = checkpoint1[i] - 1; int b = checkpoint2[i] - 1; g[a].insert(b); g[b].insert(a); } long long result = 0; REP(i, N) { result += count2Plus(g[i].size()); } // 頂点数3 for (int i = 0; i < N; ++i) { for (int j = i + 1; j < N; ++j) { for (int k = j + 1; k < N; ++k) { if (g[i].count(j) && g[j].count(k) && g[k].count(i)) { ++result; } } } } // 1本 result += checkpoint1.size(); // エッジなし ++result; return result; } }
class PenguinEmperor { public: vector<vector<ll> > mul(vector<vector<ll> >& a, vector<vector<ll> >& b) { int n = a.size(); vector<vector<ll> > out(n, vector<ll>(n)); REP(i, n) REP(j, n) { out[0][i] += a[0][j] * b[j][i] % MOD; out[0][i] %= MOD; } for (int i = 1; i < n; ++i) { REP(j, n) { out[i][j] = out[0][(i - j + n) % n]; } } return out; } int countJourneys(int N, long long daysPassed) { vector<ll> loop(N); loop[0] = 1; for (int day = 1; day <= N; ++day) { vector<ll> next(N); REP(from, N) { next[(from - day + N) % N] += loop[from]; next[(from - day + N) % N] %= MOD; if ((from - day + N) % N != (from + day) % N) { next[(from + day) % N] += loop[from]; next[(from + day) % N] %= MOD; } } swap(next, loop); } vector<vector<ll> > m(N, vector<ll>(N)); REP(i, N) REP(j, N) { m[i][j] = loop[(i + j) % N]; } vector<vector<ll> > y = m; vector<vector<ll> > v(N, vector<ll>(N)); REP(i, N) { v[i][i] = 1; } ll p = daysPassed / N; for (; p; y = mul(y, y), p >>= 1) if (p & 1) v = mul(v, y); vector<ll> way = v[0]; for (int day = 1; day <= daysPassed % N; ++day) { vector<ll> next(N); REP(from, N) { next[(from - day + N) % N] += way[from]; next[(from - day + N) % N] %= MOD; if ((from - day + N) % N != (from + day) % N) { next[(from + day) % N] += way[from]; next[(from + day) % N] %= MOD; } } swap(next, way); } return way[0]; } }
oxx 75.66 475位 2129->2013