oj.uz

Submission #987307

# Submission time Handle Problem Language Result Execution time Memory
987307 2024-05-22T14:31:27 Z alexdd Semafor (COI20_semafor) C++17
0 / 100
 135 ms 3920 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
struct matrix
{
    int v[100][100];
};
matrix operator*(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] += aux.v[i][k] * aux.v[k][j];
                aux.v[i][j]%=MOD;
            }
        }
    }
    return aux;
}
matrix put(matrix a, int exp)
{
    if(exp==1)
        return a;
    if(exp%2==0)
        return put(a*a,exp/2);
    else
        return put(a*a,exp/2)*a;
}
int m;
map<pair<int,int>,pair<int,bool>> mp;
int dp[12][1505];

int put_nr(int 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;
}
int fact[3005],invf[3005];
int 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)
{
    dp[0][0]=1;
    for(int i=1;i<=cnt1;i++)
    {
        for(int nr=0;nr<=k;nr++)
        {
            dp[i][nr]=0;
            for(int cur=1;cur<=nr;cur+=2)
            {
                dp[i][nr] += dp[i-1][nr-cur] * comb(nr,cur);
                dp[i][nr]%=MOD;
            }
        }
    }
    for(int i=cnt1+1;i<=10;i++)
    {
        for(int nr=0;nr<=k;nr++)
        {
            dp[i][nr]=0;
            for(int cur=0;cur<=nr;cur+=2)
            {
                dp[i][nr] += dp[i-1][nr-cur] * comb(nr,cur);
                dp[i][nr]%=MOD;
            }
        }
    }
    return dp[10][k];
}
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];
    }
}
signed main()
{
    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;
    for(int i=0;i<100;i++)
        for(int j=0;j<100;j++)
            rez.v[i][j]=0;
    rez.v[x][0]=1;
    if(n/k > 0) rez = rez*put(km,n/k);
    if(n%k > 0) rez = rez*rm;

    if(n==k) rez=km;

    for(int i=0;i<100;i++)
    {
        if(m==1 && i>=10)
            break;
        cout<<rez.v[x][i]<<"\n";
    }
    return 0;
}
/**
input: 2 10 10 79

*/

Subtask #1
0 / 6.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1116 KB Output is correct
2 Correct 7 ms 1116 KB Output is correct
3 Incorrect 135 ms 1224 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1116 KB Output is correct
2 Correct 7 ms 1116 KB Output is correct
3 Incorrect 135 ms 1224 KB Output isn't correct
4 Halted 0 ms 0 KB -