kmyk-jikka / Jikka

an automated solver for problems of competitive programming
https://kmyk-jikka.github.io/Jikka/playground
Apache License 2.0
152 stars 11 forks source link

mod がうまく伝播しない場合がある #178

Closed kmyk closed 2 years ago

kmyk commented 2 years ago

Summary / 概要

リストを用いて最適化を阻害しつつ Fibonacci 数を求めるコード (#153 で @riantkb さんが提出してくれたやつに mod を足したもの) において、mod を取る処理がうまく伝播してくれない

Steps to reproduce / 再現方法

$ stack run -- convert examples/wip/fib_list.py

examples/wip/fib_list.py

from typing import *

def solve(n: int) -> int:
    a = 0
    b = 1
    lis = []
    for i in range(n):
        lis.append(0)
    for i in lis:
        c = a + b + i
        a = b
        b = c
    return a % 1000000007

def main():
    n = int(input())
    ans = solve(n)
    print(ans)

if __name__ == "__main__":
    main()

environments:

Expected behavior / 期待される挙動

examples/fib.py と同様に mod が伝播されてほしい

Actual behavior / 実際の挙動

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdint>
#include <functional>
#include <iostream>
#include <numeric>
#include <string>
#include <tuple>
#include <vector>
#include "jikka/modulo_matrix.hpp"
int64_t solve(int64_t n_613) {
    std::vector<int64_t> x614;
    for (int32_t i615 = 0; i615 < int32_t(n_613); ++ i615) {
        x614.push_back(0);
    }
    int64_t x_622 = 1;
    int64_t x_623 = 0;
    for (int64_t x619 : x614) {
        int64_t x624 = x619 + x_622 + x_623;
        x_622 = x624;
        x_623 = x_622;
    }
    return jikka::modmat::floormod<2>(std::array<int64_t, 2>{x_622, x_623}, 1000000007)[1];
}
int main() {
    int64_t n_626 = -1;
    std::cin >> n_626;
    auto ans_627 = solve(n_626);
    std::cout << ans_627 << ' ';
    std::cout << '\n' << ' ';
}