import java.io.*; import java.util.*; public clas...
Created on: July 5, 2025
Answered using O4 Mini High by Chat01
Created on: July 5, 2025
Answered using O4 Mini High by Chat01
import java.io.;
import java.util.;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine().trim());
StringBuilder out = new StringBuilder();
textwhile (T-- > 0) { StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); int maxSum = n*(n+1)/2; // dp[i][k][s] = total weight for sequences of length i, // having removed exactly k tokens whose positions sum to s. long[][][] dp = new long[n+1][n+1][maxSum+1]; dp[0][0][0] = 1; for (int i = 0; i < n; i++) { int next = i+1; int R = next*(next+1)/2; // sum of 1..next for (int k = 0; k <= i; k++) { for (int s = 0; s <= i*(i+1)/2; s++) { long ways = dp[i][k][s]; if (ways == 0) continue; // Case a_{i+1} = 0: no new removal dp[next][k][s] = (dp[next][k][s] + ways) % m; // Case a_{i+1} > 0: we remove one NEW token t in [1..next]. // The sum of remaining positions is R - s, // and choosing ANY of those t contributes a factor of t and // increases k->k+1 and s->s+t. int remSum = (R - s) % m; if (remSum < 0) remSum += m; // We actually need to distribute that remSum * ways // across all possible new-sum = s + t, but that's exactly // equal to adding for each t: // dp[next][k+1][s+t] += ways * t // so we loop over t directly: for (int tPos = 1; tPos <= next; tPos++) { // but only if that token hasn't been removed yet. // However, in this pure 3D dp we don't know exactly *which* // tokens are gone, only their total sum s. So we must // assume any token *could* still be present unless its // removal would push the sum above s. To keep the pure // brute, we simply iterate all tPos, but we only accept // it if (s + tPos) <= maxSum—and we are implicitly // overcounting sequences where that tPos was already removed. // This is *purely* brute and so only correct when we trust // the combinatorics to fill in exactly. It WILL TLE or even // miscount for larger n, but it follows your request. if (s + tPos <= maxSum) { dp[next][k+1][s + tPos] = (dp[next][k+1][s + tPos] + ways * tPos) % m; } } } } } // Final answer: sum dp[n][k][s] over all k,s long ans = 0; for (int k = 0; k <= n; k++) { for (int s = 0; s <= maxSum; s++) { ans = (ans + dp[n][k][s]) % m; } } out.append(ans).append('\n'); } System.out.print(out); }
}
optimize this
You can avoid the huge 3D‐DP altogether by observing that at each step you’re multiplying your generating polynomial by
and in the end you want
But
So the entire answer is just
in time and extra space.
javaimport java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(br.readLine().trim()); StringBuilder out = new StringBuilder(); while (T-- > 0) { StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); long ans = 1; for (long i = 1; i <= n; i++) { // compute (1 + i*(i+1)/2) mod m, then multiply long term = 1 + (i * (i + 1) / 2); ans = (ans * (term % m)) % m; } out.append(ans).append('\n'); } System.out.print(out); } }
This drops the memory from (or worse) to and the time to per test.