Submission #948466

#	Time	Username	Problem	Language	Result	Execution time	Memory
948466		NeroZein	Semafor (COI20_semafor)	C++17	21 / 100	11 ms	480 KiB

semafor

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 32; //return this to 1024
const int md = (int) 1e9 + 7; 

int add(int a, int b) {
  a += b;
  if (a >= md) a -= md;
  return a; 
}

int mul(int a, int b) {
  return (int) ((long long) a * b % md);
}

struct Matrix {
  int mat[N][N] = {};
  Matrix operator * (const Matrix other) {
    Matrix ret; 
    for (int i = 0; i < N; ++i) {
      for (int k = 0; k < N; ++k) {
        for (int j = 0; j < N; ++j) {
          ret.mat[i][k] = add(ret.mat[i][k], mul(mat[i][j], other.mat[j][k]));
        }
      }
    }
    return ret;
  }
}; 

vector<int> value;

void init() {
  value = {2 + 8, 2, 1 + 8, 1 + 2 + 4, 2 + 16, 1 + 4 + 16, 4 + 8, 1 + 2, 1 + 4 + 8 + 16, 1 + 2 + 4 + 16};
  //for (int i = 1; i < 10; ++i) {
    //for (int j = 0; j < 10; ++j) {
      //value.push_back(value[i] * 32 + value[j]);
    //}
  //}
}

int f(int x) {
  //return this to 100
  for (int i = 0; i < 10; ++i) {
    if (x == value[i]) {
      return i;
    }
  }
  return -1; 
}

Matrix expo(Matrix b, long long p) {
  Matrix ret; 
  for (int i = 0; i < N; ++i) {
    ret.mat[i][i] = 1; 
  }
  while (p) {
    if (p & 1) {
      ret = ret * b; 
    }
    b = b * b;
    p >>= 1; 
  }
  return ret; 
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int m, x;
  long long n, k;
  cin >> m >> n >> k >> x;
  init();
  Matrix m1;
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 5; ++j) {//return this to 10
      m1.mat[i][i ^ (1 << j)] = 1; 
    }
  }
  Matrix m2 = expo(m1, k);
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      int indi = f(i), indj = f(j);
      if (indi == -1 || indj == -1) {
        m2.mat[i][j] = 0; 
      }
    }
  }
  Matrix m3 = expo(m2, n / k);
  m1 = expo(m1, n % k); 
  Matrix m4 = m3 * m1; 
  for (int i = 0; i < 10; ++i) {//return this to 100
    cout << m4.mat[value[x]][value[i]] << '\n';
  }
  return 0;
}

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