Submission #7161582


Source Code Expand

Copy
import sys
input = sys.stdin.readline

import numpy as np

MOD = 998244353  
N,M = map(int,input().split())

def cumprod_mod(arr):
    L = len(arr); Lsq = int((L**.5)+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

# x^n = a+bx mod 1-3x+x^2
Nsq = int((N**.5)+1)
a = np.zeros((Nsq,Nsq+1),dtype=np.int64)
b = np.zeros((Nsq,Nsq+1),dtype=np.int64)
a[0,0] = 1
for n in range(1,Nsq+1):
    a[0,n] = -b[0,n-1] % MOD; b[0,n] = (a[0,n-1]+3*b[0,n-1]) % MOD
u,v = a[0,Nsq],b[0,Nsq]
for n in range(1,Nsq):
    a[n] = (a[n-1]*u-b[n-1]*v) % MOD
    b[n] = (a[n-1]*v+b[n-1]*u+3*b[n-1]*v) % MOD
a = a[:,:-1].ravel()
b = b[:,:-1].ravel()
G = (-a-2*b) % MOD
G = G[:N+1]

A,B = -G[N-1],-G[N]+3*G[N-1]
A,B = A+B,-B
A %= MOD; B %= MOD

def fibonacci(n):
    # a+bx mod 1+x-x^2
    if n == 0:
        return 1,0
    a,b = fibonacci(n//2)
    a,b = a*a+b*b,2*a*b+b*b
    a,b = a%MOD,b%MOD
    return (b,a+b) if n&1 else (a,b)

x = (np.arange(N,dtype=np.int64)+M)%MOD
x[0] = 1
num = cumprod_mod(x)

x = np.arange(N,dtype=np.int64)
x[0] = 1
fact = cumprod_mod(x)

x = np.arange(N,0,-1,dtype=np.int64)
x[0] = pow(int(fact[-1]),MOD-2,MOD)
fact_inv = cumprod_mod(x)[::-1]

if N == 1:
    x = 0
else:
    x = ((num * fact_inv % MOD)[:N-1] * G[N-2::-1] % MOD).sum() % MOD
y,z = fibonacci(M+1)
answer = (z*A + y*B + x)%MOD
print(answer)

Submission Info

Submission Time
Task G - Sum of Fibonacci Sequence
User maspy
Language Python (3.4.3)
Score 1400
Code Size 1548 Byte
Status AC
Exec Time 237 ms
Memory 31216 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4 Subtask5
Score / Max Score 0 / 0 100 / 100 170 / 170 230 / 230 420 / 420 480 / 480
Status
AC × 3
AC × 8
AC × 13
AC × 5
AC × 13
AC × 28
Set Name Test Cases
Sample sample_1.txt, sample_2.txt, sample_3.txt
Subtask1 sample_1.txt, sample_2.txt, sample_3.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub1_in5.txt
Subtask2 sample_1.txt, sample_2.txt, sample_3.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub1_in5.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt, sub2_in5.txt
Subtask3 sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub3_in5.txt
Subtask4 sample_1.txt, sample_2.txt, sample_3.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub3_in5.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub4_in4.txt, sub4_in5.txt
Subtask5 sample_1.txt, sample_2.txt, sample_3.txt, sub1_in1.txt, sub1_in2.txt, sub1_in3.txt, sub1_in4.txt, sub1_in5.txt, sub2_in1.txt, sub2_in2.txt, sub2_in3.txt, sub2_in4.txt, sub2_in5.txt, sub3_in1.txt, sub3_in2.txt, sub3_in3.txt, sub3_in4.txt, sub3_in5.txt, sub4_in1.txt, sub4_in2.txt, sub4_in3.txt, sub4_in4.txt, sub4_in5.txt, sub5_in1.txt, sub5_in2.txt, sub5_in3.txt, sub5_in4.txt, sub5_in5.txt
Case Name Status Exec Time Memory
sample_1.txt AC 154 ms 12536 KB
sample_2.txt AC 151 ms 12424 KB
sample_3.txt AC 151 ms 12424 KB
sub1_in1.txt AC 150 ms 12424 KB
sub1_in2.txt AC 151 ms 12424 KB
sub1_in3.txt AC 152 ms 12424 KB
sub1_in4.txt AC 152 ms 12424 KB
sub1_in5.txt AC 154 ms 12536 KB
sub2_in1.txt AC 162 ms 13560 KB
sub2_in2.txt AC 191 ms 19696 KB
sub2_in3.txt AC 171 ms 15380 KB
sub2_in4.txt AC 161 ms 13520 KB
sub2_in5.txt AC 235 ms 31216 KB
sub3_in1.txt AC 150 ms 12424 KB
sub3_in2.txt AC 150 ms 12424 KB
sub3_in3.txt AC 150 ms 12424 KB
sub3_in4.txt AC 150 ms 12424 KB
sub3_in5.txt AC 151 ms 12424 KB
sub4_in1.txt AC 154 ms 12536 KB
sub4_in2.txt AC 154 ms 12424 KB
sub4_in3.txt AC 153 ms 12424 KB
sub4_in4.txt AC 152 ms 12512 KB
sub4_in5.txt AC 153 ms 12536 KB
sub5_in1.txt AC 207 ms 23228 KB
sub5_in2.txt AC 214 ms 25376 KB
sub5_in3.txt AC 207 ms 23168 KB
sub5_in4.txt AC 236 ms 31216 KB
sub5_in5.txt AC 237 ms 31216 KB