Đếm Số Xâu Nhị Phân Không Chứa 101 - DMOJ: Modern Online Judge

Trang chủ » đếm Số Xâu Con » Đếm Số Xâu Nhị Phân Không Chứa 101 - DMOJ: Modern Online Judge

Có thể bạn quan tâm

Log in or Sign up

Đếm số xâu nhị phân không chứa 101

Submit solution All submissions Best submissions Points: 4 (partial) Time limit: 1.0s Memory limit: 98M Author: TICHPX Problem types Toán rời rạc, Xâu ký tự Allowed languages Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho một số nguyên dương n bạn hãy đếm số xâu nhị phân có độ dài n mà không chứa xâu con "101"

Input

Một số tự nhiên duy nhất \(n (1 \leq n \leq 10^6)\)

Output

Số xâu nhị phân có độ dài n mà không chứa 101, kết quả có thể rất lớn bạn chỉ cần in ra phần dư của nó chia cho \(10^9+7\)

Ví dụ

Input

4

Output

12

Giải thích Có 12 xâu không chứa xâu con 101 là

0000 0001 0010 0011 0100 0110 0111 1000 1001 1100 1110 1111 tichpx

Comments

There are no comments at the moment.

⤢ ▁ Giải đáp với AI C++ (CPP) Ada AWK Classical brain C C11 COBOL CLANG CLANGX CoffeScript C++03 C++11 C++14 C++17 D language DART Fortran FORTH Assembly (x64) GO Haskell Intercal JAVA11 Java 8 LUA Mono C# Mono F# MONOVB Pascal Perl PHP PIKE Python 2 Python 3 Pypy 2 Pypy 3 LISP SCALA SCM SED TCL Gửi

Từ khóa » đếm Số Xâu Con