Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Fibonacci 数を求めるコードで内側で mod を取ると行列累乗してくれない #179

Open
kmyk opened this issue Aug 13, 2021 · 0 comments

Comments

@kmyk
Copy link
Collaborator

kmyk commented Aug 13, 2021

Summary / 概要

Fibonacci 数を求めるコードで内側で mod を取ると行列累乗してくれない。
最も外側でやる (examples/fib.py) としてくれるが、これと同様に行列累乗してほしい。

Steps to reproduce / 再現方法

$ stack run convert examples/wip/fib_alt.py

examples/wip/fib_alt.py

def f(n: int) -> int:
    a = 0
    b = 1
    for _ in range(n):
        c = (a + b) % 1000000007
        a = b
        b = c
    return a

def solve(n: int) -> int:
    return f(n)

Expected behavior / 期待される挙動

examples/fib.py みたいに行列累乗が使われてほしい

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.hpp"
#include "jikka/modulo_matrix.hpp"
int64_t solve(int64_t n_425) {
    int64_t x_429 = 1;
    int64_t x_430 = 0;
    for (int32_t i427 = 0; i427 < int32_t(n_425); ++ i427) {
        int64_t x431 = jikka::mod::plus(jikka::modmat::floormod<2>(std::array<int64_t, 2>{x_429, x_430}, 1000000007)[1], jikka::modmat::floormod<2>(std::array<int64_t, 2>{x_429, x_430}, 1000000007)[0], 1000000007);
        x_429 = x431;
        x_430 = x_429;
    }
    return x_430;
}
int main() {
    int64_t x433 = -1;
    std::cin >> x433;
    auto x434 = solve(x433);
    std::cout << x434 << ' ';
}
@kmyk kmyk added the bug Something isn't working label Aug 13, 2021
@kmyk kmyk removed the bug Something isn't working label Sep 25, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant