Tidal Lighthouse

This is a fun OI problem regarding sequences that I came up with. You can submit your solution here.

Time limit: 1.0 s · Memory limit: 128 MB · Modulus: 998244353

Background

On the cliffs of Kaer stands a lighthouse. Its beacon sits at the centre of the tower, and every year the masons add one lamp niche above it and one below, so the tower is always symmetric about the beacon: in year $k$ it holds $2k-1$ niches.

The lamps of Kaer burn with a cold, greedy flame. If two adjacent niches are lit on the same night their beams interfere and the whole tower goes dark, so the keeper must choose his pattern with care — any subset of niches, the empty one included, so long as no two chosen niches are neighbours.

The keeper is old now. His logbook devotes one page to each year of his service, and on that page he wrote down every pattern that would have been legal that year. He wants to know how many patterns are written in the whole book.

Statement

In year $k$ the tower has $2k-1$ niches in a vertical line, numbered $1$ to $2k-1$ . A pattern for year $k$ is a subset $P\subseteq\{1,\dots,2k-1\}$ containing no two consecutive integers. Let $w(k)$ be the number of such patterns.

Given $n$ , compute

$S(n)=\sum_{k=1}^{n} w(k) \pmod{998244353}.$

There are $T$ independent queries.

Input

Line 1: integer $T$ . Next $T$ lines: one integer $n$ each.

Output

$T$ lines, $S(n)\bmod 998244353$ .

Sample 1

Explanation. Year 1: one niche, patterns $\varnothing,\{1\}$ , so $w(1)=2$ . Year 2: three niches, $w(2)=5$ , running total $7$ . Year 3: five niches, $w(3)=13$ , total $20$ .

Sample 2

3
1000000
1000000000000000000
123456789012345678

140464712
962211619
66528294

Constraints

For all data: $1\le T\le 10^5$ , $1\le n\le 10^{18}$ .

Subtask	Points	$n\le$	$T\le$
1	8	$10$	$10$
2	12	$10^6$	$10$
3	15	$10^6$	$10^5$
4	20	$10^{18}$	$1$
5	45	$10^{18}$	$10^5$

Click to reveal solution

Step 1 — identify $w$

$w(k)$ counts independent sets on a path of $2k-1$ vertices. Conditioning on the last niche gives the Fibonacci recurrence, so a path of $m$ vertices has $F_{m+2}$ independent sets ( $F_1=F_2=1$ ), hence

$w(k)=F_{2k+1}.$

Only odd-indexed Fibonacci numbers appear. The familiar $\sum_{k\le m}F_k=F_{m+2}-1$ does not apply.

Step 2 — the odd-index identity

Write each term as a difference and telescope:

$F_{2k+1}=F_{2k+2}-F_{2k}$

$\sum_{k=1}^{n}F_{2k+1}=\sum_{k=1}^{n}\big(F_{2k+2}-F_{2k}\big)=F_{2n+2}-F_2$

$\boxed{\,S(n)=F_{2n+2}-1\,}$

Check: $S(1)=F_4-1=3-1=2$ . ✓ $S(2)=F_6-1=8-1=7$ . ✓

The two companion identities worth knowing: $\sum_{k=1}^{n}F_{2k-1}=F_{2n},\qquad \sum_{k=1}^{n}F_{2k}=F_{2n+1}-1.$

Step 3 — one Fibonacci number, fast

Fast doubling ( $F_{2m}=F_m(2F_{m+1}-F_m)$ , $F_{2m+1}=F_m^2+F_{m+1}^2$ ) or the $2\times2$ matrix power gives $F_{2n+2}$ in $O(\log n)$ . Total $O(T\log n)$ .

Overflow trap: the index is $2n+2$ , up to $2\cdot10^{18}+2$ . It fits in a signed 64-bit integer, but only just — and it will silently break any 32-bit index.

Reference solution

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
const u64 MOD = 998244353;

pair<u64,u64> fib(u64 n){            // {F(n), F(n+1)}, F(0)=0, F(1)=1
    if(!n) return {0,1};
    auto [a,b] = fib(n>>1);
    u64 c = a * ((2*b % MOD + MOD - a) % MOD) % MOD;
    u64 d = (a*a + b*b) % MOD;
    if(n & 1) return {d, (c+d)%MOD};
    return {c, d};
}
int main(){
    int T; scanf("%d",&T);
    while(T--){
        u64 n; scanf("%llu",&n);
        printf("%llu\n", (fib(2*n+2).first + MOD - 1) % MOD);
    }
}