Contest Duration: - (local time) (180 minutes)

Submission #7161582

Source Code Expand

Copy
```import sys

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

#### Submission Info

Submission Time 2019-08-27 14:22:14+0900 G - Sum of Fibonacci Sequence maspy Python (3.4.3) 1400 1548 Byte AC 237 ms 31216 KB

#### Judge Result

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