第11届浙江大学校赛比赛点评beta » ZOJ3482py

ZOJ3482py
ZOJ3482py.py


re = input()
for ri in xrange(re):
	n, m, base = map(int, raw_input().split())
	a = map(int, raw_input().split())

	dp = [[1 if i == m - 1 else 0 for j in xrange(n)] for i in xrange(m)]
	pre = [range(n) for i in xrange(m)]
	for i in xrange(m - 2, -1, -1):
		for j in xrange(n):
			if dp[i + 1][j]:
				next
			for k in xrange(n):
				prod = dp[i + 1][j] * max(0, (a[j] - a[k]))
				if dp[i][k] < prod or (dp[i][k] == prod and pre[i][k] > j):
					dp[i][k] = prod
					pre[i][k] = j

	k = 0
	for i in range(n):
		if dp[0][k] < dp[0][i]:
			k = i
	print dp[0][k] % base
	if dp[0][k]:
		b = []
		for i in range(m):
			b.append(k)
			k = pre[i][k]
	else:
		b = [0 for i in xrange(m)]
	print " ".join(map(str, b))
Leave a Reply