Submission #562912

#	Time	Username	Problem	Language	Result	Execution time	Memory
562912		Redhood	Semafor (COI20_semafor)	C++14	100 / 100	123 ms	616 KiB

semafor

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(), (x).end()

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;






typedef long long ll;
typedef long double ld;

#define int long long
int Cnk[11][11];
const int mod = (int)1e9 + 7;
const ll mod2 = 1ll * mod * mod;
template<typename T>
void md(T &a){
    if(a >= mod)
        a-=mod;
}
template<typename T>
void md2(T &a){
    if(a >= mod2)
        a-=mod2;
}
int B;
struct mat{
    vector<vector<int>>a;
    int n , m;
    mat(){
        n = m = B;
        a.resize(n , vector < int > (m));
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j)
                a[i][j]=0;
    }
    mat(int _n, int _m){
        n = _n , m = _m;
        a.resize(n , vector < int > (m));
        for(int i=0;i<n;++i)
            for(int j=0;j<m;++j){
                a[i][j] = 0;
            }
    }
};

mat operator*(const mat&a , const mat&b){
    mat c(a.n, b.m);
    assert(a.m == b.n);
    for(int i = 0; i < a.n; ++i){
        for(int j = 0; j < b.m;++j){
            ll f = 0;
            for(int k = 0; k < a.m; ++k){
                f += (1ll * a.a[i][k] * b.a[k][j]);
                md2(f);
            }
            c.a[i][j] = f % mod;
        }
    }
    return c;
}
mat one(int f){
    mat c(f , f);
    for(int i = 0; i < f; ++i)
        c.a[i][i] = 1;
    return c;
}
mat binpow(const mat &a , ll b){
    if(b == 0){
        return one(a.n);
    }
    mat ans = binpow(a , b / 2);
    ans = ans * ans;
    if(b & 1)
        ans = ans * a;
    return ans;
}
int binpow_num(int a , int b){
    if(b == 0)
        return 1;
    int ans = binpow_num(a , b / 2);
    ans = (1ll * ans * ans) % mod;
    if(b & 1)
        ans = (1ll * ans * a) % mod;
    return ans;
}
int INV(int x){
    return binpow_num(x , mod - 2);
}



signed main(){
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);

    /// n a b c d e
    /// 0 0 1 0 1 0
    /// 1 0 1 0 0 0
    /// 2 1 0 0 1 0
    /// 3 1 1 1 0 0
    /// 4 0 1 0 0 1
    /// 5 1 0 1 0 1
    /// 6 0 0 1 1 0
    /// 7 1 1 0 0 0
    /// 8 1 0 1 1 1
    /// 9 1 1 1 0 1

    string st[10];
    st[0] ="01010";
    st[1] ="01000";
    st[2]="10010";
    st[3]= "11100";
    st[4]= "01001";
    st[5]= "10101";
    st[6]= "00110";
    st[7]= "11000";
    st[8]= "10111";
    st[9]= "11101";



    vector<int> id(10), f;
    for(int i = 0; i < 10; ++i){
        id[i] = 0;
        for(int j = 0; j < 5; ++j){
            if(st[i][j] == '1')
                id[i] += (1 << j);
        }
    }
    f = id;
    sort(all(f));
    f.erase(unique(all(f)), f.end());
    assert(sz(f) == 10);




    int m, x;
    ll n ,k ;
    cin >> m >> n >> k >> x;
    B = m * 5 + 1;


    auto get_msk = [&](int ff){
        int msk = 0;
        if(m == 1){
            msk = id[ff];
        }else{
            msk = ((id[ff / 10])<<5)|(id[ff%10]);
        }
        return msk;
    };



    vector < int > get(100);
    vector < int > cnt(10);

    for(int i = 0; i < 11; ++i){
        Cnk[i][0]=1;
        for(int j = 1; j <= i; ++j){
            Cnk[i][j] = Cnk[i - 1][j] + Cnk[i - 1][j - 1];
            md(Cnk[i][j]);
        }
    }

    mat trans(B,B);
    for(int i = 0; i < B; ++i){
        for(int j = 0; j < B; ++j){

            if(abs(i - j) > 1)
                continue;
            if(i == j)
                continue;
            if(i + 1 == j)
                trans.a[i][j] = 1ll * (B-1 - i)% mod;
            else
                trans.a[i][j] = 1ll * i % mod;
        }
    }

    mat trans1 = trans;
    trans = binpow(trans1 , k);




    int states = 10;
    if(m == 2)states *= 10;


    mat ST(states , states);


    mat init(1 , B);
    init.a[0][0] = 1;
    trans = init * trans;
    for(int i = 0; i < states; ++i) {
        for(int j = 0 ; j < states; ++j){
            int t = __builtin_popcount(get_msk(i) ^ get_msk(j));

            assert(t < B);
        //            if(t >= B){
//                cout << "FUKK " << i << ' ' << j << endl;
//                cout << get_msk(i) << ' ' << get_msk(j) << endl;
//                exit(0);
//            }

            ST.a[i][j] = (1ll * trans.a[0][t] * INV(Cnk[B-1][t])) % mod;
        }
    }

//
//    for(int i = 0; i < states; ++i){
//        for(int j = 0;  j < states; ++j){
//            cout << ST.a[i][j] << ' ';
//        }
//        cout << '\n';
//    }


    mat INIT(1 , states);


    INIT.a[0][x] = 1;

    ST = INIT * binpow(ST , n / k);

    trans =trans1;
    trans = binpow(trans , n % k);

//
//    for(int i = 0; i < 10; ++i)
//        cout << ST.a[0][i] << ' ';
//    cout << endl;

    vector < int > ans(states);


//    cerr << states << endl;
    for(int i = 0; i < states; ++i) {
        for(int j = 0 ; j < states; ++j){
            int t = __builtin_popcount(get_msk(i) ^ get_msk(j));
            assert(t < B);
            ans[j] += 1ll * ST.a[0][i] * 1ll * trans.a[0][t] % mod * INV(Cnk[B-1][t]) % mod;
            md(ans[j]);
        }
    }

    for(int i = 0; i < states; ++i){
        cout << ans[i] << '\n';
    }


    return 0;
}

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