oj.uz

Submission #381549

# Submission time Handle Problem Language Result Execution time Memory
381549 2021-03-25T09:43:31 Z topovik Semafor (COI20_semafor) C++14
0 / 100
 5 ms 748 KB 
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define len(x) x.size()
#define debug(x) cout << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef long double ld;

const ll N = 32;
const ll oo = 1e9 + 7;

const ll valid[10] = {8 + 2, 2, 8 + 1, 1 + 2 + 4, 2 + 16, 1 + 4 + 16, 8 + 4, 1 + 2, 1 + 4 + 8 + 16, 1 + 2 + 4 + 16};


ll sum(ll x, ll y)
{
    return (x + y) % oo;
}

ll mult(ll x, ll y)
{
    return (x * y) % oo;
}

vector <vector <ll> > mult(vector <vector <ll> > a, vector <vector <ll> > b)
{
    vector <vector <ll> > c;
    c.resize(N);
    for (ll i = 0; i < N; i++) c[i].resize(N);
    for (ll i = 0; i < N; i++)
        for (ll j = 0; j < N; j++)
        {
            for (ll c1 = 0; c1 < N; c1++) c[i][j] = sum(c[i][j], mult(a[i][c1], b[c1][j]));
        }
    return c;
}

vector <vector <ll> > binpow(vector <vector <ll> > c, ll k)
{
    if (k == 1) return c;
    if (k & 1) return mult(c, binpow(c, k - 1));
    else
    {
        vector <vector <ll> > c1 = binpow(c, k / 2);
        return mult(c1, c1);
    }
}

int main()
{
    vector <vector <ll> > b;
    vector <vector <ll> > a;
    ll m, n, k, x;
    cin >> m >> n >> k >> x;
    b.resize(N);
    for (ll i = 0; i < N; i++) b[i].resize(N);
    for (ll i = 0; i < N; i++)
        for (ll j = 0; (1 << j) < N; j++) b[i][i ^ (1 << j)] = 1, b[i ^ (1 << j)][i] = 1;
    a = binpow(b, k);
    vector <vector <ll> > c;
    c.resize(N);
    for (ll i = 0; i < N; i++) c[i].resize(N);
    for (ll i = 0; i < 10; i++)
        for (ll j = 0; j < 10; j++) c[valid[i]][valid[j]] = a[valid[i]][valid[j]];
    a = c;
    a = binpow(a, n / k);
    if (n % k != 0) a = mult(binpow(b, n % k), a);
    for (ll i = 0; i < 10; i++) cout << a[valid[x]][valid[i]] << "\n";
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Incorrect 2 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Incorrect 2 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 748 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -