Sereja and Equality
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x.
For two permutations P1 and P2 Sereja found new function F(P1, P2) that is equal to number of pairs (l,r) (1 <= l <= r <= n) such that P1[l..r] is almost equal to P2[l..r] and array P1[l..r] contain not more then E inversions.
Now Sereja is insterested in next question: what is the sum F(P1,P2) by all possible permutations P1, P2 from n elements.
First line contain integer T - number of testcases. T tests follow. The only line of each testcase contain integers n, E.
For each testcase output answer modulo 1000000007 (10^9+7).
- 1 ≤ T ≤ 10000
- 1 ≤ n ≤ 500
- 1 ≤ E ≤ 1000000
Input: 4 2 2 2 1 2 0 1 1 Output: 10 10 9 1
|Tags||dynamic-programming, hard, july14, maths, sereja|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.