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



Sample input:
2 998244353


Sample output:
3

Submission status: Wrong Answer

Solution code:
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(0, n, c):
        ndp[i:] += dp[:n-i]
    dp = ndp % m #更新する

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

Submission status: Wrong Answer

Solution code:
def main():
    n,m=map(int,input().split())
    from itertools import accumulate
    dp=[[0] * (n+1)]*n 
    #print(dp)
    dp[0][-n]=1
    for i in range(n-1):
        dp[i]=list(accumulate(dp[i]))
        for j in range(1,n+1):
            dp[i+1][j]=dp[i][j]
    cnt=0
    for i in range(n):
        cnt+=dp[i][-1]
        cnt%=m
    print(cnt)
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M=map(int, input().split())
ans=0
for a in range(1, N+1):
  for b in range(a, N+1):
    ans=ans+((min(N, a+b-1)-b+1)**(N-2))%M
print(ans)

Submission status: Wrong Answer

Solution code:
def factorial( n) : 
	M = 1000000007
	f = 1
	for i in range(1, n + 1): 
		f = f * i 
	return f % M

Submission status: Time Limit Exceeded

Solution code:
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:
    w = np.zeros(n, dtype=np.int64)
    w[::c] = 1
    dp = np.convolve(dp, w, mode='full')[:n] % m

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
    # 面倒なので2べきに
    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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
n_l=[i for i in range(1,n+1)]
ans=0
import itertools
l1=list(itertools.combinations(n_l))
for i in range(len(l1)):
	for j in range(2**n):
		l2=[0]*n
		for k in range(n//2):
			if (j>>k) & 1:
				l2[k]=1
		flag=True
		cnt1=0
		cnt2=0
		for l in range(n):
				if l2[l]:
					cnt1+=l1[l]
				else:
					cnt2+=l1[l]
		if cnt2>cnt1:
			ans+=1
print(ans)

Submission status: Runtime Error

Solution code:
n,a,b=map(int,input().split())
c=abs(a-b)
if(c%2==0):
    print(int(c/2))
else:
    d=(a+b+1)/2
    e=(2*n+2-a-b+1)/2
    f=min(d,e)
    print(int(f))