oj.uz

Submission #987359

# Submission time Handle Problem Language Result Execution time Memory
987359 2024-05-22T16:12:50 Z alexdd Semafor (COI20_semafor) C++17
0 / 100
 63 ms 1324 KB 
#include<iostream>
#include<map>
using namespace std;
#define int long long
const long long MOD = 1e9+7;
struct matrix
{
    int v[105][105];
};
matrix inm(matrix x, matrix y)
{
    matrix aux;
    for(int i=0;i<100;i++)
    {
        for(int j=0;j<100;j++)
        {
            aux.v[i][j]=0;
            for(int k=0;k<100;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 dp[1505][12];

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);
}
int calc(int cnt1, int k)
{
    if(k%2!=cnt1%2)
        return 0;
    dp[0][0]=1;
    for(int nr=0;nr<=k;nr++)
    {
        for(int cur=0;cur<=10;cur++)
        {
            if(cur>0) dp[nr][cur] += dp[nr-1][cur-1]*(10-cur);
            if(cur<10) dp[nr][cur] += dp[nr-1][cur+1]*(cur+1);
            dp[nr][cur]%=MOD;
        }
    }
    return dp[k][cnt1] * put_nr(comb(10,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++)
        {
            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()
{
    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);

    //if(n==k) rez=km;

    for(int i=0;i<100;i++)
    {
        cout<<rez.v[x][i]<<"\n";
    }
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 1324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 1324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1112 KB Output isn't correct
2 Halted 0 ms 0 KB -