1

Всем доброго времени суток, задача такая: Найти элемент произведения (с заданными i и j) какого-то количества матриц. При вычислении произведения применяется следующее правило - если результат операции выходит большим либо равным некоторого простого числа P (часть входных данных), то результат этой операции заменяется на остаток от деления на число P. Задача отсюда, под буквой C.

Проблема во времени выполнения - я написал некоторый код, выполняющийся верно, однако вычисление всего произведения занимает слишком много времени. Кажется, нужно считать только необходимую часть матричного произведения, но я не могу понять, какую именно. Подскажите, пожалуйста!

Входные данные:

3 2

1 2

239

1 2
3 4

4 2
1 3

1 2
2 1

Выходные данные:

20

Написанная мной программа:

#include <iostream>
#include <iomanip>
using namespace std;
 
void Nullify(int matrix[][201], int n)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            matrix[i][j] = 0;
        }
    }
}
 
void Multiple(int mat1[][201], int mat2[][201], int mat3[][201], int n, int p)
{
    Nullify(mat3, n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            for (int k = 1; k <= n; k++)
            {
                mat3[i][j] += ((mat1[i][k] * mat2[k][j]) % p);
                mat3[i][j] %= p;
            }
        }
    }
}
 
void InputMatrix(int matrix[][201], int n)
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> matrix[i][j];
        }
    }
}
 
int main()
{
    int currentMatrix[201][201] = { 0 };
    int result[201][201] = { 0 };
    int temp[201][201] = { 0 };
     
    int quanity;
    int n;
 
    int x, y;
 
    int p;
 
    cin >> quanity >> n;
    cin >> x >> y;
    cin >> p;
 
    bool flag = true;
 
    InputMatrix(temp, n);
 
    for (int i = 0; i < quanity - 1; i++)
    {
        InputMatrix(currentMatrix, n);
        if (flag)
        {
            Multiple(temp, currentMatrix, result, n, p);
            flag = false;
        }
        else
        {
            Multiple(result, currentMatrix, temp, n, p);
            flag = true;
        }
    }
     
    if (flag)
    {
        cout << temp[x][y];
    }
    else
    {
        cout << result[x][y];
    }
 
     
}
4
  • 2
    Как обычно - дайте-ка URL задания, чтобы посмотреть в оригинале...
    – Harry
    Commented 7 дек. 2020 в 15:09
  • @Harry, В вопросе оставил ссылку (в виде гиперссылки) на задачу, но дублирую: neerc.ifmo.ru/school/io/archive/20051112/problems-advanced.pdf (задача C) Commented 7 дек. 2020 в 15:20
  • 1
    А проверяющей системы нет?..
    – Harry
    Commented 7 дек. 2020 в 15:29
  • @Harry, да, конечно, вот задача на ACMP, стоило сразу прикрепить эту ссылку: acmp.ru/index.asp?main=task&id_task=557 Commented 7 дек. 2020 в 15:32

2 ответа 2

3

Ну, в общем, идея в том, что не надо m*n*n*n операций - всю матрицу считать. Достаточно взять только a-ю строку, и работать с ней (ну сами смотрите формулу умножения... если нас интересует только элемент в a-й строке...)

Но все это так и не хотело работать, пока не вспомнил, что GNU-сные компиляторы страшно ускоряют чтение с помощью двух строк отвязки от синхронизации с вводом-выводом C. И тут оно таки заработало...

Вобщем, вот...

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

    int m, n, a, b, p;
    cin >> m >> n >> a >> b >> p;
    --a; --b;
    vector<int> A(n), C(n);

    cin.ignore(100000,'\n');
    cin.ignore(100000,'\n');

    for(int i = 0; i < n; ++i)
    {
        if (i == a)
            for(int j = 0; j < n; ++j) cin >> A[j];
        cin.ignore(100000,'\n');
    }

    for(int k = 1; k < m; ++k)
    {
        C = vector<int>(n);
        for(int l = 0; l < n; ++l)
        {
            for(int j = 0; j < n; ++j)
            {
                int x;
                cin >> x;
                C[j] += A[l]*x;
            }
        }
        for(int l = 0; l < n; ++l)
            A[l] = C[l]%p;
    }
    cout << A[b] << endl;
}

Только уж постарайтесь понять сами, как оно работает, ладно? :)

0

Во первых, обнуление элементов матрицы(функция Nullify) совершенно лишняя операция, так как вы потом все равно их инициализируете. Соответственно, из функции Multiple уберите ее вызов.

Во вторых, Последнюю матрицу не нужно умножать. Если результат умножения всех предыдущих матриц, это матрица result(если матриц всего два, то result это первая матрица), то нужно просто вывести сумму умножения строки result[x] на столбец y последней матрицы. Но последняя матрица тоже не нужна в принципе, потому что вы просто можете читать столбец из потока ввода:

int answer = 0, t;
for (int i = 0; i < n; ++i) {
    for (int j = 0; j <= y; ++j) {
        cin >> t;  //читаем пока не дойдем до элемента соответствующего столбца
        cin.ignore(n, '\n'); //пропускаем остальную строку
    }
    answer += result[x][i] * t;
}
cout << answer%p;

  

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.