Submission #987369

#	Time	Username	Problem	Language	Result	Execution time	Memory
987369		alexdd	Semafor (COI20_semafor)	C++17	100 / 100	292 ms	1880 KiB

semafor

#include<iostream>
#include<map>
using namespace std;
#define int long long
const long long MOD = 1e9+7;
int DIM;
struct matrix
{
    int v[105][105];
};
matrix inm(matrix x, matrix y)
{
    matrix aux;
    for(int i=0;i<DIM;i++)
    {
        for(int j=0;j<DIM;j++)
        {
            aux.v[i][j]=0;
            for(int k=0;k<DIM;k++)
            {
                aux.v[i][j] += 1LL*x.v[i][k] * y.v[k][j]%MOD;
                aux.v[i][j]%=MOD;
            }
        }
    }
    return aux;
}
matrix unu;
matrix put(matrix a, int exp)
{
    matrix aux=unu;
    while(exp>0)
    {
        if(exp%2==1) aux = inm(aux,a);
        a = inm(a,a);
        exp/=2;
    }
    return aux;
}
int m;
map<pair<int,int>,pair<int,bool>> mp;
long long put_nr(long long a, int exp)
{
    if(exp==0)
        return 1;
    if(exp%2==0)
        return put_nr(a*a%MOD,exp/2);
    else
        return put_nr(a*a%MOD,exp/2)*a%MOD;
}
long long fact[3005],invf[3005];
long long comb(int x, int y)
{
    if(x<y)
        return 0;
    return ((((fact[x]*invf[y])%MOD)*invf[x-y])%MOD);
}
matrix dp;
int calc(int cnt1, int k)
{
    if(k%2!=cnt1%2)
        return 0;
    DIM=11;
    for(int i=0;i<11;i++)
        for(int j=0;j<11;j++)
            dp.v[i][j]=0;
    for(int cur=0;cur<=m*5;cur++)
    {
        if(cur>0) dp.v[cur][cur-1] = m*5-(cur-1);
        if(cur<10) dp.v[cur][cur+1] = cur+1;
    }
    dp = put(dp,k);
    DIM=100;
    return dp.v[cnt1][0] * put_nr(comb(m*5,cnt1),MOD-2)%MOD;
}
int getmp(int config, int k)
{
    int cnt1=0;
    for(int i=0;i<10;i++)
        if(((1<<i)&config))
            cnt1++;
    if(mp[{cnt1,k}].second==0)
    {
        mp[{cnt1,k}]={calc(cnt1,k),1};
    }
    return mp[{cnt1,k}].first;
}
int mask[100];
matrix calc_matrix(int k)
{
    matrix aux;
    for(int i=0;i<100;i++)
    {
        for(int j=0;j<100;j++)
        {
            if(m==1 && (i>9 || j>9)) aux.v[i][j]=0;
            else aux.v[i][j] = getmp((mask[i]^mask[j]),k);
        }
    }
    return aux;
}
void calc_mask()
{
    mask[0] = (1<<1) + (1<<3);
    mask[1] = (1<<1);
    mask[2] = (1<<0) + (1<<3);
    mask[3] = (1<<0) + (1<<1) + (1<<2);
    mask[4] = (1<<1) + (1<<4);
    mask[5] = (1<<0) + (1<<2) + (1<<4);
    mask[6] = (1<<2) + (1<<3);
    mask[7] = (1<<0) + (1<<1);
    mask[8] = (1<<0) + (1<<2) + (1<<3) + (1<<4);
    mask[9] = (1<<0) + (1<<1) + (1<<2) + (1<<4);
    for(int i=10;i<100;i++)
    {
        mask[i] = (mask[i/10]<<5) + mask[i%10];
    }
    for(int i=9;i>=0;i--)
        mask[i] += (mask[0]<<5);
}
signed main()
{
    DIM=100;
    for(int i=0;i<100;i++)
        for(int j=0;j<100;j++)
            unu.v[i][j]=0;
    for(int i=0;i<100;i++)
        unu.v[i][i]=1;

    fact[0]=1;
    for(int i=1;i<=3000;i++)
        fact[i]=fact[i-1]*i%MOD;
    invf[3000]=put_nr(fact[3000],MOD-2);
    for(int i=2999;i>=0;i--)
        invf[i]=invf[i+1]*(i+1)%MOD;

    int n,k,x;
    cin>>m>>n>>k>>x;
    calc_mask();
    matrix km = calc_matrix(k);
    matrix rm = calc_matrix(n%k);
    matrix rez=unu;
    if(n/k > 0) rez = inm(rez,put(km,n/k));
    if(n%k > 0) rez = inm(rez,rm);

    for(int i=0;i<100;i++)
    {
        if(m==1 && i>9)
            break;
        cout<<rez.v[x][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