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());
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
textlong[] dp = new long[n+1]; dp[0] = 1; for (int p = n; p >= 1; p--) { long[] next = new long[n+1]; int done = n - p + 1; for (int t = 0; t <= done; t++) { long cur = dp[t]; if (cur == 0) continue; next[t] = (next[t] + cur) % m; int avail = done - t; if (avail > 0) { next[t+1] = (next[t+1] + cur * avail % m * p) % m; } } dp = next; } long total = 0; for (long x : dp) { total = (total + x) % m; } sb.append(total).append('\n'); } System.out.print(sb); }
}
can we simplify this code
Here’s a cleaned‐up, more concise version of your DP solution that:
javaimport java.io.*; import java.util.*; public class Main { static class FastReader { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String next() throws IOException { String s; while ((s = br.readLine()) != null && s.isEmpty()) {} return s; } int nextInt() throws IOException { return Integer.parseInt(next().trim().split("\\s+")[0]); } } public static void main(String[] args) throws IOException { FastReader in = new FastReader(); int T = in.nextInt(); StringBuilder out = new StringBuilder(); while (T-- > 0) { String[] nm = in.next().trim().split("\\s+"); int n = Integer.parseInt(nm[0]), mod = Integer.parseInt(nm[1]); long[] dp = new long[n + 1]; long[] next = new long[n + 1]; dp[0] = 1; // Place values p = n, n-1, ..., 1 for (int p = n; p >= 1; p--) { Arrays.fill(next, 0); // done = how many positions already filled: n - p + 1 int done = n - p + 1; for (int taken = 0; taken <= done; taken++) { long ways = dp[taken]; if (ways == 0) continue; // Option 1: leave the new slot empty next[taken] = (next[taken] + ways) % mod; // Option 2: fill one of the (done - taken) free slots with one of p items int free = done - taken; if (free > 0) { next[taken + 1] = (next[taken + 1] + ways * free % mod * p) % mod; } } // swap dp and next long[] tmp = dp; dp = next; next = tmp; } // sum up all ways long total = 0; for (long w : dp) total = (total + w) % mod; out.append(total).append('\n'); } System.out.print(out); } }
What’s improved?
StringTokenizer
.next
is allocated just once outside the loop and zeroed via Arrays.fill()
, saving GC churn.taken
instead of t
, ways
instead of cur
, free
instead of avail
.dp
and next
to avoid repeated allocations.This version behaves identically but is shorter, easier to read, and marginally faster by reusing memory.