Submission #55562909

---

Source Code Expand

import sys,math,random
from heapq import heappush,heappop
from bisect import bisect_right,bisect_left
from collections import Counter,deque,defaultdict

# functions #
MOD = 998244353
RANDOM = random.randrange(2**62)
def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return a//gcd(a,b)*b
def w(x):
    return x ^ RANDOM
##

#String hashing : sh, fenwick sortedlist : fsortl, sieve : sieve, SparseTable : SparseTable
#bucket sorted list : bsortl, segment tree(lazy propogation) : SegmentTree, bootstrap : bootstrap
#binary indexed tree : BIT, segment tree(point updates) : SegmentPoint, Convex Hull : hull
#Combinatorics : pnc
#Template : https://github.com/OmAmar106/Template-for-Competetive-Programming

def solve():
    n = int(sys.stdin.readline().strip())
    L = list(map(int, sys.stdin.readline().split()))
    ans = [0 for i in range(n)]
    # dp[i][nofe][diff]++
    dp = [[{} for i in range(n+1)] for j in range(n)]
    for i in range(n):
        dp[i][1][0] = 1
        ans[0] += 1
        for j in range(i-1,-1,-1):
            f = L[i]-L[j]
            if f in dp[i][2]:
                dp[i][2][f] += 1
            else:
                dp[i][2][f] = 1
            ans[1] += 1
            for k in range(2,n):
                if f in dp[j][k]:
                    if f in dp[i][k+1]:
                        dp[i][k+1][f] += dp[j][k][f]
                    else:
                        dp[i][k+1][f] = dp[j][k][f]
                    ans[k] += dp[j][k][f]
                    ans[k] %= MOD
                    dp[i][k+1][f] %= MOD
    for i in range(len(ans)):
        ans[i] %= MOD
    print(*ans)
    #L1 = list(map(int, sys.stdin.readline().split()))
    #st = sys.stdin.readline().strip()
solve()

Submission Info

Judge Result