Submission #480824

#	Time	Username	Problem	Language	Result	Execution time	Memory
480824		Rainbowbunny	Semafor (COI20_semafor)	C++17	100 / 100	285 ms	1356 KiB

semafor

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 5;
const int mod = 1e9 + 7;

int Add(int x, int y)
{
    return x + y >= mod ? x + y - mod : x + y;
}

int Sub(int x, int y)
{
    return x - y < 0 ? x - y + mod : x - y;
}

int Mul(int x, int y)
{
    return 1ll * x * y % mod;
}

int BinPow(int n, long long k)
{
    int ans = 1, cur = n;
    while(k)
    {
        if(k & 1)
        {
            ans = Mul(ans, cur);
        }
        cur = Mul(cur, cur);
        k >>= 1;
    }
    return ans;
}

int fact[MAXN], ifact[MAXN];

int C(int k, int n)
{
    if(k > n or k < 0)
    {
        return 0;
    }
    return Mul(fact[n], Mul(ifact[k], ifact[n - k]));
}

void MulM(vector <vector <int> > &A, vector <vector <int> > B)
{
    int n = A.size();
    vector <vector <int> > C(n, vector <int> (n, 0));
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            for(int k = 0; k < n; k++)
            {
                C[i][j] = Add(C[i][j], Mul(A[i][k], B[k][j]));
            }
        }
    }
    swap(A, C);
}

void BinPowM(vector <vector <int> > &A, long long k)
{
    int n = A.size();
    vector <vector <int> > B(n, vector <int> (n));
    for(int i = 0; i < n; i++)
    {
        B[i][i] = 1;
    }
    while(k)
    {
        if(k & 1)
        {
            MulM(B, A);
        }
        MulM(A, A);
        k >>= 1;
    }
    swap(A, B);
}

int m, x;
int a[] = {10, 8, 18, 28, 9, 21, 6, 24, 23, 29};
long long n, k;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    fact[0] = 1;
    for(int i = 1; i < MAXN; i++)
    {
        fact[i] = Mul(fact[i - 1], i);
    }
    ifact[MAXN - 1] = BinPow(fact[MAXN - 1], mod - 2);
    for(int i = MAXN - 2; i >= 0; i--)
    {
        ifact[i] = Mul(ifact[i + 1], i + 1);
    }
    cin >> m >> n >> k >> x;
    if(m == 1)
    {
        vector <vector <int> > DP(6, vector <int> (6, 0));
        vector <vector <int> > Cnt(6, vector <int> (6, 0));
        DP[0][0] = 1;
        for(int i = 0; i < 6; i++)
        {
            if(i < 5)
            {
                Cnt[i][i + 1] = 5 - i;
            }
            if(i > 0)
            {
                Cnt[i][i - 1] = i;
            }
        }
        BinPowM(Cnt, k);
        MulM(DP, Cnt);
        for(int i = 0; i < 6; i++)
        {
            DP[0][i] = Mul(DP[0][i], BinPow(C(i, 5), mod - 2));
        }
        vector <vector <int> > Ans(10, vector <int> (10, 0));
        vector <vector <int> > NDP(10, vector <int> (10, 0));
        Ans[0][x] = 1;
        for(int i = 0; i < 10; i++)
        {
            for(int j = 0; j < 10; j++)
            {
                NDP[i][j] = DP[0][__builtin_popcount(a[i] ^ a[j])];
            }
        }
        BinPowM(NDP, n / k);
        MulM(Ans, NDP);
        n %= k;
        for(int i = 0; i < 6; i++)
        {
            for(int j = 0; j < 6; j++)
            {
                DP[i][j] = 0;
                Cnt[i][j] = 0;
            }
        }
        DP[0][0] = 1;
        for(int i = 0; i < 6; i++)
        {
            if(i < 5)
            {
                Cnt[i][i + 1] = 5 - i;
            }
            if(i > 0)
            {
                Cnt[i][i - 1] = i;
            }
        }
        BinPowM(Cnt, n);
        MulM(DP, Cnt);
        for(int i = 0; i < 6; i++)
        {
            DP[0][i] = Mul(DP[0][i], BinPow(C(i, 5), mod - 2));
        }
        for(int i = 0; i < 10; i++)
        {
            for(int j = 0; j < 10; j++)
            {
                NDP[i][j] = DP[0][__builtin_popcount(a[i] ^ a[j])];
            }
        }
        MulM(Ans, NDP);
        for(int i = 0; i < 10; i++)
        {
            cout << Ans[0][i] << '\n';
        }
    }
    else
    {
        vector <vector <int> > DP(11, vector <int> (11, 0));
        vector <vector <int> > Cnt(11, vector <int> (11, 0));
        DP[0][0] = 1;
        for(int i = 0; i < 11; i++)
        {
            if(i < 10)
            {
                Cnt[i][i + 1] = 10 - i;
            }
            if(i > 0)
            {
                Cnt[i][i - 1] = i;
            }
        }
        BinPowM(Cnt, k);
        MulM(DP, Cnt);
        for(int i = 0; i < 11; i++)
        {
            DP[0][i] = Mul(DP[0][i], BinPow(C(i, 10), mod - 2));
        }
        vector <vector <int> > Ans(100, vector <int> (100, 0));
        vector <vector <int> > NDP(100, vector <int> (100, 0));
        Ans[0][x] = 1;
        for(int i = 0; i < 100; i++)
        {
            for(int j = 0; j < 100; j++)
            {
                int t1 = i / 10, t2 = j / 10, t3 = i % 10, t4 = j % 10;
                NDP[i][j] = DP[0][__builtin_popcount(a[t1] ^ a[t2]) + __builtin_popcount(a[t3] ^ a[t4])];
            }
        }
        BinPowM(NDP, n / k);
        MulM(Ans, NDP);
        n %= k;
        for(int i = 0; i < 11; i++)
        {
            for(int j = 0; j < 11; j++)
            {
                DP[i][j] = 0;
                Cnt[i][j] = 0;
            }
        }
        DP[0][0] = 1;
        for(int i = 0; i < 11; i++)
        {
            if(i < 10)
            {
                Cnt[i][i + 1] = 10 - i;
            }
            if(i > 0)
            {
                Cnt[i][i - 1] = i;
            }
        }
        BinPowM(Cnt, n);
        MulM(DP, Cnt);
        for(int i = 0; i < 11; i++)
        {
            DP[0][i] = Mul(DP[0][i], BinPow(C(i, 10), mod - 2));
        }
        for(int i = 0; i < 100; i++)
        {
            for(int j = 0; j < 100; j++)
            {
                int t1 = i / 10, t2 = j / 10, t3 = i % 10, t4 = j % 10;
                NDP[i][j] = DP[0][__builtin_popcount(a[t1] ^ a[t2]) + __builtin_popcount(a[t3] ^ a[t4])];
            }
        }
        MulM(Ans, NDP);
        for(int i = 0; i < 100; i++)
        {
            cout << Ans[0][i] << '\n';
        }
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 15 / 15
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 15 / 15
• Subtask 6: 40 / 40