結果

問題 No.1783 Remix Sum
ユーザー qwewe
提出日時 2025-05-14 13:27:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,594 bytes
コンパイル時間 1,364 ms
コンパイル使用メモリ 95,324 KB
実行使用メモリ 817,280 KB
最終ジャッジ日時 2025-05-14 13:27:50
合計ジャッジ時間 5,895 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other MLE * 1 -- * 75
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <map>

using namespace std;

long long N_balls_in; 
int K_digits;
long long M_ops;
int T_threshold;

const long long MOD = 120586241;

// Helper to get digits of a number (little-endian: d_0, d_1, ...)
// Example: n=123, k_digits=5 -> {3, 2, 1, 0, 0}
vector<int> get_digits(long long n, int k_digits) {
    vector<int> digits(k_digits, 0); 
    string s = to_string(n);
    int len_s = s.length();
    for (int i = 0; i < len_s; ++i) {
        digits[i] = s[len_s - 1 - i] - '0'; 
    }
    return digits;
}

// Helper to form number from digits (little-endian)
// Example: {3, 2, 1, 0, 0} -> 123
long long get_num(const vector<int>& digits) {
    long long num = 0;
    long long power_of_10 = 1;
    for (int digit_val : digits) { 
        num += (long long)digit_val * power_of_10;
        power_of_10 *= 10;
    }
    return num;
}

// Matrix multiplication: C = A * B
vector<vector<long long>> multiply_matrix(const vector<vector<long long>>& A, const vector<vector<long long>>& B, int size) {
    vector<vector<long long>> C(size, vector<long long>(size, 0));
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            // C[i][j] = sum(A[i][l] * B[l][j]) over l
            // Note: For A[i][l]*B[l][j] to not overflow long long before modulo,
            // MOD*MOD should be < MAX_LONGLONG. (1.2e8)^2 = 1.44e16, fits in signed long long.
            unsigned long long current_sum = 0; 
            for (int l = 0; l < size; ++l) {
                current_sum += (unsigned long long)A[i][l] * B[l][j];
                 if (current_sum >= (unsigned long long)MOD * MOD ) { // Heuristic to keep sum smaller and prevent overflow if it gets too large
                    current_sum %= MOD;
                }
            }
            C[i][j] = current_sum % MOD;
        }
    }
    return C;
}

// Matrix power: A^m
vector<vector<long long>> matrix_pow(vector<vector<long long>> A, long long m, int size) {
    vector<vector<long long>> res(size, vector<long long>(size, 0));
    for (int i = 0; i < size; ++i) res[i][i] = 1;

    // Ensure A elements are already mod MOD (they should be by construction)
    // for (int r = 0; r < size; ++r) for (int c = 0; c < size; ++c) A[r][c] %= MOD;


    while (m > 0) {
        if (m % 2 == 1) res = multiply_matrix(res, A, size);
        A = multiply_matrix(A, A, size);
        m /= 2;
    }
    return res;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N_balls_in >> K_digits >> M_ops >> T_threshold;

    map<long long, int> ball_counts_map;
    for (int i = 0; i < N_balls_in; ++i) {
        long long val;
        cin >> val;
        ball_counts_map[val]++;
    }

    long long max_val_state = 1;
    for (int i = 0; i < K_digits; ++i) {
        max_val_state *= 10;
    }
    
    if (M_ops == 0) {
        for (long long i = 0; i < max_val_state; ++i) {
            if (i == 0) cout << 1 << "\n";
            else cout << 0 << "\n";
        }
        return 0;
    }
    
    int matrix_size = max_val_state;
    vector<vector<long long>> T_matrix(matrix_size, vector<long long>(matrix_size, 0));

    // Pre-calculate all x_digits to avoid repeated conversions
    vector<vector<int>> x_digits_cache(matrix_size);
    for(long long x=0; x<matrix_size; ++x) {
        x_digits_cache[x] = get_digits(x, K_digits);
    }

    for(auto const& [y_val, count_y] : ball_counts_map) { 
        vector<int> y_digits = get_digits(y_val, K_digits);

        for (long long x = 0; x < max_val_state; ++x) {
            const vector<int>& x_digits = x_digits_cache[x];
            
            vector<int> z_digits(K_digits);
            bool sad = false;
            for (int i = 0; i < K_digits; ++i) { 
                if (i < T_threshold) {
                    if (x_digits[i] + y_digits[i] >= 10) {
                        sad = true;
                        break;
                    }
                    z_digits[i] = x_digits[i] + y_digits[i];
                } else {
                    z_digits[i] = (x_digits[i] + y_digits[i]) % 10;
                }
            }

            if (!sad) {
                long long z_val = get_num(z_digits);
                T_matrix[z_val][x] = (T_matrix[z_val][x] + count_y) % MOD;
            }
        }
    }
    
    vector<vector<long long>> T_matrix_M = matrix_pow(T_matrix, M_ops, matrix_size);
    
    for (long long i = 0; i < max_val_state; ++i) {
        cout << T_matrix_M[i][0] << "\n";
    }

    return 0;
}
0