Problem:
 Score : 1200 points    Problem Statement N problems have been chosen by the judges, now it's time to assign scores to them!  Problem i must get an integer score A_i between 1 and N , inclusive.
The problems have already been sorted by difficulty: A_1 \le A_2 \le \ldots \le A_N must hold.
Different problems can have the same score, though.  Being an ICPC fan, you want contestants who solve more problems to be ranked higher.
That's why, for any k ( 1 \le k \le N-1 ), you want the sum of scores of any k problems to be strictly less than the sum of scores of any k+1 problems.  How many ways to assign scores do you have? Find this number modulo the given prime M .      Constraints  2 \leq N \leq 5000  9 \times 10^8 < M < 10^9  M is a prime.  All input values are integers.         Input Input is given from Standard Input in the following format:  N  M       Output Print the number of ways to assign scores to the problems, modulo M .        Sample Input 1 2 998244353      Sample Output 1 3  The possible assignments are (1, 1) , (1, 2) , (2, 2) .       Sample Input 2 3 998244353      Sample Output 2 7  The possible assignments are (1, 1, 1) , (1, 2, 2) , (1, 3, 3) , (2, 2, 2) , (2, 2, 3) , (2, 3, 3) , (3, 3, 3) .       Sample Input 3 6 966666661      Sample Output 3 66       Sample Input 4 96 925309799      Sample Output 4 83779

Solution (Python):
N,M=map(int,input().split())
DP=[[-1]*6000 for i in range(6000)]
def P(n,k):
  if n<0 or k<1:
    return 0
  if DP[n][k]!=-1:
    return DP[n][k]
  if k==1:
    DP[n][k]=1
    return 1
  DP[n][k]=(P(n,k-1)+P(n-k,k))%M
  return DP[n][k]

for i in range(5500):
  for j in range(i+1):
    P(i+1,j+1)
X=[0]
DP[0][0]=1
for i in range(5500):
  X.append(0)
  for j in range(i+1):
    X[-1]=(X[-1]+DP[j][j]*DP[i-j][i-j])%M
Y=[0]
for i in range(10800):
  Y.append(Y[i]+X[i>>1])
P=0
for i in range(1,N+1):
  P=(P+X[i])%M
  if 2*i>N:
    P=(P-Y[2*i-N])%M
print(P)

Solution (Python):
import numpy as np 
n,m=map(int, input().split())
coef = np.minimum(np.arange(n,1,-1),np.arange(1,n))
dp = np.zeros(n, dtype=np.int64)
dp[0] = 1
for c in coef:
    ndp = dp.copy()
    for i in range(c, n, c):
        ndp[i:] += dp[:n-i]
    dp = ndp % m 

print((dp*np.arange(n, 0, -1) % m).sum() % m)

Solution (Python):
import numpy as np

n, m = map(int, input().split())

coef = np.minimum(np.arange(n, 1, -1), np.arange(1, n))
dp = np.zeros(n, dtype=np.int64)
dp[0] = 1
for c in coef:
    ndp = dp.copy()
    for i in range(c, n, c):
        ndp[i:] += dp[:n - i]
    dp = ndp % m

print((dp * np.arange(n, 0, -1) % m).sum() % m)

Solution (Python):
import numpy as np

n, m = map(int, input().split())

coef = np.minimum(np.arange(n, 1, -1), np.arange(1, n))
dp = np.zeros(n, dtype=np.int64)
dp[0] = 1
for c in coef:
    ndp = np.zeros(n, dtype=np.int64)
    for i in range(0, n, c):
        ndp[i:] += dp[:n - i]
    dp = ndp % m

print((dp * np.arange(n, 0, -1) % m).sum() % m)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,MOD = map(int,read().split())

def cumprod(A, MOD = MOD):
    L = len(A); Lsq = int(L**.5+1)
    A = np.resize(A, Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        A[:,n] *= A[:,n-1]; A[:,n] %= MOD
    for n in range(1,Lsq):
        A[n] *= A[n-1,-1]; A[n] %= MOD
    return A.ravel()[:L]
def make_fact(U, MOD = MOD):
    x = np.arange(U, dtype = np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact,fact_inv

U = 10 ** 5
fact, fact_inv = make_fact(U)
inv = np.zeros(U,np.int64)
inv[1:] = fact[:-1] * fact_inv[1:] % MOD

def fft_convolve(f, g, MOD = MOD):
    """
    数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
    30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
    """
    fft = np.fft.rfft; ifft = np.fft.irfft
    Lf = len(f); Lg = len(g); L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fl = f & (1 << 15) - 1; fh = f >> 15
    gl = g & (1 << 15) - 1; gh = g >> 15
    conv = lambda f,g: ifft(fft(f,fft_len) * fft(g,fft_len))[:L]
    x = conv(fl, gl) % MOD
    y = conv(fl+fh, gl+gh) % MOD
    z = conv(fh, gh) % MOD
    a, b, c = map(lambda x: (x + .5).astype(np.int64), [x,y,z])
    return (a + ((b - a - c) << 15) + (c << 30)) % MOD

def fps_exp(h,MOD=MOD):
    
    L = len(h)
    i = (L-1).bit_length()
    N = (1 << i)
    h = np.resize(h,N)
    dh = np.empty_like(h)
    dh[0:N-1] = h[1:N] * np.arange(1,N,dtype=np.int64) % MOD
    f = np.zeros_like(h); g = np.zeros_like(h)
    f[:2] = np.array([1,h[1]],np.int64); g[0] = 1; m = 2
    while m <= N//2:
        fg = fft_convolve(f[:m],g[:m],MOD)[:m]
        fgg = fft_convolve(fg,g[:m],MOD)[:m]
        g[:m] *= 2; g[:m] -= fgg; g %= MOD
        q = dh[:m-1]
        s = np.zeros(m+m,np.int64); s[1:m] = f[1:m] * np.arange(1,m,dtype=np.int64) % MOD
        r = fft_convolve(f[:m],q,MOD)
        s[1:1+len(r)] -= r
        s[0:m] += s[m:m+m]
        s = s[:m] % MOD
        t = fft_convolve(g[:m],s,MOD)[:m]
        t *= inv[m:m+m]; t %= MOD
        u = h[m:m+m] - t; u %= MOD
        v = fft_convolve(f,u,MOD)[:m]
        f[m:m+m] += v
        m *= 2
    return f[:L]

f = np.zeros((N+N+10),np.int64)
for x in range(1,N//2+1):
    f[x::x] += 2 * inv[1:(len(f)-1) // x + 1]
if N & 1:
    x = (N+1)//2
    f[x::x] += inv[1:(len(f)-1) // x + 1]

g = fps_exp(f)
answer = g[:N].sum() % MOD
print(answer)

Solution (Python):
N,M=map(int,input().split())
A = list(range(1,N//2+1))*2
if N&1:A+=[(N+1)//2]
d=[1]+[0]*(N+N)
for x in A:
  for i in range(N+1):
    d[i]%=M
    d[i+x]+=d[i]
print(sum(d[:N])%M)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・N=6とする。
・[1,1,1,1,1,1],[0,1,1,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1,1],[0,0,0,0,1,1],[0,0,0,0,0,1],[0,0,0,0,0,0]
合計ちょうど6個の線形結合 → 任意の単調数列。最初のやつは1回以上使わなければいけない。
・1,0,-1,-2,-2,-1,0 合計5個で0以上を作る
・-1,0,1,2,2,1,0 合計5個で0以下を作る
・0,1,2,3,3,2,1 合計5個で5以下を作る
・1,2,3,3,2,1 任意個数で5以下を作る
"""

N,MOD = map(int,read().split())

if N % 2 == 0:
    A = list(range(1,N//2+1))*2
else:
    A = list(range(1,N//2+1))*2+[(N+1)//2]

A.sort()


dp = [1] + [0] * (N+N+10)
for x in A:
    for i in range(N+1):
        dp[i] %= MOD
        dp[i+x] += dp[i]

answer = sum(dp[:N]) % MOD
print(answer)