Submission #381549

#	Time	Username	Problem	Language	Result	Execution time	Memory
381549		topovik	Semafor (COI20_semafor)	C++14	0 / 100	5 ms	748 KiB

semafor

#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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40