### DEAMN's blog

By DEAMN, history, 3 weeks ago,
• I can't think of a DP for this task help plz Find the number of sequences (a1, a2,..., an) such that a[i]^2 + a[i + 1]^2 + ... + a[n]^2 = k a[i] <= a[i + 1] <= ... <= a[n]

• T is testcase

• n is quantity of number
• k is a[i]^2 + a[i + 1]^2 + ... + a[n]^2 = k
• 1 <= T <= 1e5

• 1 <= n <= 100
• 1 <= k <= 5000
• example
• input
• 1
• 4 243
• output
• 9
• Explanation

• first 1 1 4 15 -> (1 * 1) + (1 * 1) + (4 * 4) + (15 * 15) = 243 — second 1 3 8 13 — third 1 7 7 12 — fouth 3 3 9 12 — fifth 3 4 7 13 — sixth 3 7 8 11 — seventh 4 5 9 11 — eighth 5 5 7 12 — nineth 7 7 8 9

• +23

 » 3 weeks ago, # |   0 Auto comment: topic has been updated by DEAMN (previous revision, new revision, compare).
 » 3 weeks ago, # |   0 Auto comment: topic has been updated by DEAMN (previous revision, new revision, compare).
 » 3 weeks ago, # |   0 Auto comment: topic has been updated by DEAMN (previous revision, new revision, compare).
 » 3 weeks ago, # |   0 Auto comment: topic has been updated by DEAMN (previous revision, new revision, compare).
 » 3 weeks ago, # | ← Rev. 2 →   +2 Consider DP[LEN][SUM][LAST] — number of non-decreasing sequences with length LEN, last element — LAST, and sum of squares — SUM. $DP[LEN][SUM][LAST] = \sum_{i = 0}^{LAST}DP[LEN - 1][SUM - LAST^2][i]$ $ANSWER[n][k] = \sum_{i = 0}^{\sqrt{k}}DP[n][k][i]$To calculate sum - for every pair {LEN, SUM} build cumulative sum arrays.Let: $K = max\{k\}, N = max\{n\}$Note: $LAST^2 \leq K$Total complexity: $O(N \cdot K \cdot \sqrt{K} + T \cdot \sqrt{K})$
•  » » 3 weeks ago, # ^ |   0 thx
 » 3 weeks ago, # |   0 You can also try think like this-> Suppose dp[i][j] is the number of sorted sequences having last term i and has sum of squares of its elements j. Then it's obvious dp[i][j] = dp[1][j-i*i] + dp[2][j-i*i] + dp[3][j-i*i] ...dp[i][j-i*i]Now try to think about the initial conditions, I leave this task to you :)
•  » » 3 weeks ago, # ^ |   0 dp[1][j * j] = 1?
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 Pretty close...It should be dp[1][j] = 1 (j>=1) (Why?) also I think there more conditions, Can u figure it out?