2020牛客國慶集訓派對day2 F-SUM OF SUB RECTANGLE AREAS

題意

給一個N*N的矩陣，每一位上都是1，求所有子矩陣的權值之和，

思路

設 n = 3 ； 設n = 3； 設n=3；
考慮子矩陣大小為 i ? j i * j i?j的個數 x x x，即該大小的所有子矩陣的權值為 x ? i ? j x* i * j x?i?j，
1 ? 2 1 * 2 1?2子矩陣:每行個數為 2 2 2個，有 3 3 3列，即總權值為 2 ? 3 ? （ 1 ? 2 ） ? ? 2 ? 3 2 * 3 * （1 * 2）--2 * 3 2?3?（1?2）??2?3為該矩陣在n*n矩陣中的個數， 1 ? 2 1 * 2 1?2為該子矩陣里的權值，
2 ? 3 2 * 3 2?3子矩陣：每兩行有 1 1 1個，一共 2 2 2個兩行，權值為 2 ? 3 2*3 2?3，即總權值為 1 ? 2 ? 2 ? 3 1 * 2 * 2 * 3 1?2?2?3，

根據上面推匯出：在 n ? n n*n n?n的矩陣中，有 i ? j i*j i?j子矩陣的個數為 ( n ? i + 1 ) ? ( n ? j + 1 ) (n - i + 1) * (n - j + 1) (n?i+1)?(n?j+1)，即總權值為 ( n ? i + 1 ) ? ( n ? j + 1 ) ? i ? j (n - i + 1) * (n - j + 1) * i * j (n?i+1)?(n?j+1)?i?j，
即總答案為：
a n s = ∑ i = 1 n ∑ j = 1 n ( n ? i + 1 ) ? ( n ? j + 1 ) ? i ? j ans=\sum_{i=1}^n\sum_{j=1}^n(n - i + 1) * (n - j + 1) * i * j ans=i=1∑n?j=1∑n?(n?i+1)?(n?j+1)?i?j

a n s = [ ∑ i = 1 n ( n ? i + 1 ) i ] 2 ans=[\sum_{i=1}^n(n-i+1)i]^2 ans=[i=1∑n?(n?i+1)i]2

a n s = [ n 2 ( n + 1 ) 2 ? n ( n + 1 ) ( 2 n + 1 ) 6 + n ( n + 1 ) 2 ] 2 ans=[\frac{n^2(n+1)}{2}-\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}]^2 ans=[2n2(n+1)??6n(n+1)(2n+1)?+2n(n+1)?]2

a n s = [ n ? ( n + 1 ) ? ( n + 2 ) 6 ] 2 ans=[\frac{n * (n + 1)*(n+ 2)}{6}]^2 ans=[6n?(n+1)?(n+2)?]2

因為題目說會爆longlong，所以我這里用的是JAVA大數BigInteger，python也可（不過我不會），

Code(71MS)

import java.util.*;
import java.math.*;

public class Main
{
	public static void main(String[] args){
		Scanner in = new Scanner(System.in);
        int T;
        T = in.nextInt();
        for(int i = 1;i <= T; i++) {
		    long n;
		    n = in.nextLong();
		    BigInteger ans = new BigInteger("1");
            ans = ans.multiply(BigInteger.valueOf(n));
            ans = ans.multiply(BigInteger.valueOf(n + 1));
            ans = ans.multiply(BigInteger.valueOf(n + 2));
		    ans = ans.divide(BigInteger.valueOf(6));
		    ans = ans.multiply(ans);
		    System.out.println(ans);
	    }
    }
}