Submission #560540

#	Time	Username	Problem	Language	Result	Execution time	Memory
560540		leaked	Semafor (COI20_semafor)	C++17	100 / 100	279 ms	720 KiB

semafor

#include <bits/stdc++.h>

#define f first
#define s second
#define m_p make_pair
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x) (int)(x).size()
#define pw(x) (1LL<<(x))

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
const int N=1e2+1;
const int M=1e9+7;
const ll MOD=1ll*M*M;
struct mat{
    int a[N][N];
    mat(){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++)
                a[i][j]=0;
        }
    }
    mat operator *(const mat &o){
        mat c;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                ll cur=0;
                for(int k=0;k<N;k++){
                    cur+=1ll*a[i][k]*o.a[k][j];
                    if(cur>=MOD)
                        cur-=MOD;
                }
                c.a[i][j]=cur%M;
            }
        }
        return c;
    }
};

mat binpow(mat a,int x,ll k){
    mat ans;
    ans.a[x][x]=1;
    while(k){
        if(k&1) ans=ans*a;
        a=a*a;k>>=1;
    }
    return ans;
}
int binpowt(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=1ll*ans*a%M;
        a=1ll*a*a%M;b>>=1;
    }
    return ans;
}
int C[N][N];
int inv(int x){
    return binpowt(x,M-2);
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
int di[10];
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    di[1]=0+2+0+0+0;
    di[2]=1+0+0+8+0;
    di[3]=1+2+4+0+0;
    di[4]=0+2+0+0+16;
    di[5]=1+0+4+0+16;
    di[6]=0+0+4+8+0;
    di[7]=1+2+0+0+0;
    di[8]=1+0+4+8+16;
    di[9]=1+2+4+0+16;
    di[0]=0+2+0+8+0;
    C[0][0]=1;
    for(int i=1;i<N;i++){
        for(int j=0;j<=i;j++){
            C[j][i]=C[j][i-1]+(j?C[j-1][i-1]:0);
            C[j][i]%=M;
        }
    }
    int m;ll n,k;
    int x;
    cin>>m>>n>>k>>x;
    mat me;
    for(int i=0;i<=5*m;i++){
        if((i-1)>=0)
            me.a[i][i-1]=i;
        if(i+1<=(5*m))
            me.a[i][i+1]=(5*m-i);
//        for(int j=0;j<=5*m;j++)
//            cout<<me.a[i][j]<<' ';
//        cout<<endl;
    }
    mat yo=binpow(me,0,k);
    mat yo1=binpow(me,0,n%k);
    mat o,o1;
    for(int i=0;i<(m==1?10:100);i++){
        for(int j=0;j<(m==1?10:100);j++){
            int fi=(m==1?__builtin_popcount(di[i]^di[j]):__builtin_popcount(di[i%10]^di[j%10])+__builtin_popcount(di[i/10]^di[j/10]));
            o.a[i][j]=mult(inv(C[fi][5*m]),yo.a[0][fi]);
//            cout<<"GO "<<i<<' '<<j<<' '<<' '<<fi<<' '<<o.a[i][j]<<' '<<C[fi][5*m]<<endl;
            o1.a[i][j]=mult(inv(C[fi][5*m]),yo1.a[0][fi]);
        }
    }
//    for(int i=0;i<(m==1?10:100);i++){
//        for(int j=0;j<(m==1?10:100);j++){
//            cout<<o.a[i][j]<<' ';
//        }
//        cout<<'\n';
//    }
    o=binpow(o,x,n/k);
//    for(int i=0;i<(m==1?10:100);i++){
//        for(int j=0;j<(m==1?10:100);j++){
//            cout<<o.a[i][j]<<' ';
//        }
//        cout<<'\n';
//    }
    o=o*o1;
    for(int x=0;x<(m==1?10:100);x++){
        int cur=0;
        for(int y=0;y<(m==1?10:100);y++){
            cur+=o.a[y][x];
            cur%=M;
        }
        cout<<cur<<'\n';
    }
    return 0;
}
/*
10 1
2 5 8 4 10 7 9 6 1
3
1 4
*/

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