Submission #987306

#	Time	Username	Problem	Language	Result	Execution time	Memory
987306		alexdd	The Collection Game (BOI21_swaps)	C++17	Compilation error	0 ms	0 KiB

swaps

#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

*/

Compilation message (stderr)

/usr/bin/ld: /tmp/cc1R6GLs.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccPqbU9u.o:swaps.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc1R6GLs.o: in function `main':
grader.cpp:(.text.startup+0x67): undefined reference to `solve(int, int)'
collect2: error: ld returned 1 exit status