fork download 
  1. import os, sys, getpass, platform
  2. import math, random, decimal, queue, heapq, bisect, itertools, functools, collections, string, operator, timeit, pprint
  3. from queue import Queue, PriorityQueue, LifoQueue
  4. from itertools import accumulate, chain, combinations, combinations_with_replacement, compress, count, cycle, dropwhile, filterfalse, groupby, islice, permutations, product, repeat, starmap, takewhile, tee, zip_longest
  5. from functools import cmp_to_key, lru_cache, partial, partialmethod, reduce, singledispatch, total_ordering
  6. from random import choice, choices, shuffle, sample, random, randint, randrange, uniform, seed, getstate, setstate, getrandbits
  7. from string import ascii_letters, ascii_lowercase, ascii_uppercase, digits, hexdigits, octdigits, punctuation, printable, whitespace
  8. from heapq import heapify, heappush, heappop, heapreplace, nlargest, nsmallest
  9. from bisect import bisect, bisect_left
  10. from collections import defaultdict, OrderedDict, deque, Counter
  11. from math import gcd, factorial, isqrt, comb, perm, prod
  12.  
  13. cond = False
  14.  
  15.  
  16. I = lambda: [int(a) for l in sys.stdin for a in l.strip().split()]
  17. S = lambda: [a for l in sys.stdin for a in l.strip().split()]
  18. IM = lambda: [[int(a) for a in l.split()] for l in sys.stdin]
  19. SM = lambda: [[a for a in l.split()] for l in sys.stdin]
  20. D = lambda k=1: {i: list(map(int, input().split())) for i in range(1, 1 + int(input()) * k)}
  21. DS = lambda: {i: [(int(x[0]), x[1]) for _ in range(int(input()))
  22.                   for x in [input().split()]] for i in range(int(input()))}
  23.  
  24. d8 = ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1))
  25. d4 = ((1, 0), (0, 1), (-1, 0), (0, -1))
  26. az, AZ = ascii_lowercase, ascii_uppercase
  27. mod, inf = 1_000_000_007, float('inf')
  28. CNR = lambda n, r: factorial(n) // (factorial(r) * factorial(n - r))
  29. PNR = lambda n, r: factorial(n) // factorial(r)
  30.  
  31. A = IM()
  32.  
  33. if cond:
  34.     print(A)
  35.  
  36.  
  37. def solution(A):
  38.     def f(arr):
  39.         n, k, p = arr
  40.         dp = [[0] * (k + 1) for _ in range(2)]
  41.         dp[0][0] = 1
  42.         prev = [[0] * (k + 1) for _ in range(2)]
  43.  
  44.         for i in range(1, n + 2):
  45.             ndp = [[0] * (k + 1) for _ in range(2)]
  46.             psum = [0, 0]
  47.             for j in range(2):
  48.                 for x in range(k + 1):
  49.                     psum[j] += dp[j][x]
  50.                     psum[j] %= p
  51.             for j in range(2):
  52.                 a, b = 0, 0
  53.                 for x in reversed(range(k + 1)):
  54.                     ndp[j][x] += psum[j]
  55.                     ndp[j][x] += b
  56.                     ndp[j][x] %= p
  57.                     a += prev[j ^ 1][k - x]
  58.                     a %= p
  59.                     b += a
  60.                     b %= p
  61.             prev = dp
  62.             dp = ndp
  63.  
  64.         return (dp[0][0] - dp[1][0] + p) % p
  65.  
  66.     for i in range(1, len(A)):
  67.         s = A[i]
  68.         print(f(s))
  69.  
  70.  
  71. solution(A)
Success #stdin #stdout 0.35s 11444KB
comments (?)
stdin 
4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353
stdout 
4
7
10
456615865
https://ideone.com/sX2cW3
language:
Python 3 (python  3.12)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!