답안 #239053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
239053 2020-06-14T09:22:46 Z ne4eHbKa Mate (COCI18_mate) C++17
100 / 100
1304 ms 35076 KB
#include <bits/stdc++.h>
using namespace std;

#define ft first
#define sd second

const int N = 2020;
const int A = 26;
const int md = 1e9 + 7;
const int Q = 5e5 + 5;

void madd(int &a, int b) {a += b; while(a < 0) a += md; while(a >= md) a -= md;}
int msum(int a, int b) {a += b; while(a < 0) a += md; while(a >= md) a -= md; return a;}
void mmul(int &a, int b) {a = 1ll * a * b % md;}
int mpro(int a, int b) {return 1ll * a * b % md;}

int mpow(int a, int p) {
    int ans = 1;
    for(int i = 1 << 30; i; i >>= 1) {
        mmul(ans, ans);
        if(p & i) mmul(ans, a);
    }
    return ans;
}

int n, q;
string s;
int t[Q];
char x[Q], y[Q];

int fact[N], ifact[N];

int C(int n, int k) {return mpro(mpro(ifact[k], ifact[n - k]), fact[n]);}

struct z {
    map<int, int> u;
    vector<int> c, g, f;
    int n;

    void add(int i, bool r) { u[i] += r; }

    void init() {
        n = u.size();
        c.resize(n);
        g.resize(n);
        f.resize(n);

        int i = 0;
        for(const auto &j : u) {
            c[i] = j.ft;
            g[i] = j.sd;
            f[i++] = 0;
        }

        for(int i = 0; i < n; ++i)
            for(int j = i; j < n; ++j)
                if(g[j]) madd(f[i], mpro(g[j], C(c[j], c[i])));
    }

    int get(int x) { return f[lower_bound(c.begin(), c.end(), x) - c.begin()]; }
} f[A][A];

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
#endif

    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    for(int i = 0; i < N; ++i) fact[i] = !i ? 1 : mpro(fact[i - 1], i);
    for(int i = 0; i < N; ++i) ifact[i] = mpow(fact[i], md - 2);

    cin >> s >> q;

    n = s.size();
    for(int j = 0; j < n; ++j)
        for(int i = 0; i < j; ++i)
            f[s[i] - 'a'][s[j] - 'a'].add(i, true);

    for(int i = 0; i < q; ++i) {
        cin >> t[i] >> x[i] >> y[i];
        t[i] -= 2, x[i] -= 'a', y[i] -= 'a';
        f[x[i]][y[i]].add(t[i], false);
    }

    for(int i = 0; i < A; ++i)
        for(int j = 0; j < A; ++j)
            f[i][j].init();

    for(int i = 0; i < q; ++i)
        cout << f[x[i]][y[i]].get(t[i]) << '\n';
}

Compilation message

mate.cpp: In function 'int main()':
mate.cpp:83:15: warning: array subscript has type 'char' [-Wchar-subscripts]
         f[x[i]][y[i]].add(t[i], false);
               ^
mate.cpp:83:21: warning: array subscript has type 'char' [-Wchar-subscripts]
         f[x[i]][y[i]].add(t[i], false);
                     ^
mate.cpp:91:23: warning: array subscript has type 'char' [-Wchar-subscripts]
         cout << f[x[i]][y[i]].get(t[i]) << '\n';
                       ^
mate.cpp:91:29: warning: array subscript has type 'char' [-Wchar-subscripts]
         cout << f[x[i]][y[i]].get(t[i]) << '\n';
                             ^
# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 1920 KB Output is correct
2 Correct 12 ms 1536 KB Output is correct
3 Correct 13 ms 1664 KB Output is correct
4 Correct 19 ms 2176 KB Output is correct
5 Correct 98 ms 7160 KB Output is correct
6 Correct 96 ms 7416 KB Output is correct
7 Correct 72 ms 6392 KB Output is correct
8 Correct 66 ms 5880 KB Output is correct
9 Correct 1251 ms 35076 KB Output is correct
10 Correct 1304 ms 35064 KB Output is correct