oj.uz

답안 #557795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557795 2022-05-06T03:58:50 Z Yazan_Alattar Semafor (COI20_semafor) C++14
12 / 100
 1076 ms 276316 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 1057;
const ll inf = 2e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-6;
const int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
const int block = 320;

struct Matrix{
    vector < vector <ll> > a = vector < vector <ll> > (100, (vector <ll> (100)));

    Matrix operator *(Matrix b){
        Matrix ret;
        for(int i = 0; i < 100; ++i) for(int j = 0; j < 100; ++j) for(int k = 0; k < 100; ++k){
            ret.a[i][k] = (ret.a[i][k] + (a[i][j] * b.a[j][k])) % mod;
        }
        return ret;
    }

};

Matrix Pow(Matrix x, ll p)
{
    Matrix ret;
    for(int i = 0; i < 100; ++i) ret.a[i][i] = 1;
    while(p){
        if(p % 2) ret = ret * x;
        x = x * x;
        p /= 2;
    }
    return ret;
}

ll m, n, k, x, sticks[M], stick[M], dp[17][M][M], ans[M];
bool vist[M];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    // =======Construction=========
    sticks[1] = 2;  sticks[2] = 9;
    sticks[3] = 7;  sticks[4] = 18;
    sticks[5] = 21; sticks[6] = 12;
    sticks[7] = 3;  sticks[8] = 29;
    sticks[9] = 23; sticks[0] = 10;

    for(int i = 0; i <= 99; ++i) stick[i] = sticks[i / 10] * 32 + sticks[i % 10];

    for(int i = 0; i <= 99; ++i) vist[stick[i]] = 1;
    // =============================

    cin >> m >> n >> k >> x;

    for(int i = 0; i <= 99; ++i) dp[0][stick[i]][stick[i]] = 1;
    for(int i = 1; i <= k; ++i)
        for(int j = 0; j < 1024; ++j)
            for(int j2 = 0; j2 < 1024; ++j2)
                for(int bit = 0; bit < 10; ++bit)
                    if(vist[j] || i % k)
                        dp[i][j][j2] = (dp[i][j][j2] + dp[i - 1][j][j2 ^ (1 << bit)]) % mod;

    Matrix init;
    for(int i = 0; i <= 99; ++i) for(int j = 0; j <= 99; ++j) init.a[i][j] = dp[k][stick[i]][stick[j]];
    Matrix res = Pow(init, n / k - 1);

    for(int i = 0; i <= 99; ++i)
        for(int j = 0; j <= 99; ++j)
            for(int l = 0; l <= 99; ++l)
                ans[i] = (ans[i] + ((dp[k][stick[x]][stick[j]] * res.a[j][l]) % mod) * dp[n % k][stick[l]][stick[i]]) % mod;

    for(int i = 0; i <= 99; ++i) cout << ans[i] << endl;
    return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 2064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 59 ms 2064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 632 ms 78300 KB Output is correct
2 Runtime error 1076 ms 276192 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 720 ms 95492 KB Output is correct
2 Correct 202 ms 10736 KB Output is correct
3 Correct 285 ms 19256 KB Output is correct
4 Correct 941 ms 112548 KB Output is correct
5 Correct 286 ms 10700 KB Output is correct
6 Correct 980 ms 112504 KB Output is correct
7 Correct 675 ms 70108 KB Output is correct
8 Correct 234 ms 2212 KB Output is correct
9 Correct 224 ms 2304 KB Output is correct
10 Correct 987 ms 121060 KB Output is correct
11 Correct 77 ms 2252 KB Output is correct
12 Correct 63 ms 2280 KB Output is correct
13 Correct 393 ms 27848 KB Output is correct

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 720 ms 95492 KB Output is correct
2 Correct 202 ms 10736 KB Output is correct
3 Correct 285 ms 19256 KB Output is correct
4 Correct 941 ms 112548 KB Output is correct
5 Correct 286 ms 10700 KB Output is correct
6 Correct 980 ms 112504 KB Output is correct
7 Correct 675 ms 70108 KB Output is correct
8 Correct 234 ms 2212 KB Output is correct
9 Correct 224 ms 2304 KB Output is correct
10 Correct 987 ms 121060 KB Output is correct
11 Correct 77 ms 2252 KB Output is correct
12 Correct 63 ms 2280 KB Output is correct
13 Correct 393 ms 27848 KB Output is correct
14 Runtime error 1054 ms 276316 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 632 ms 78300 KB Output is correct
2 Runtime error 1076 ms 276192 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -