EOJ 3.30 B. 蛇形矩阵【找规律/待补】

【链接】：https://acm.ecnu.edu.cn/contest/59/problem/B/

B. 蛇形矩阵

Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

蛇形矩阵是我最喜欢的矩阵之一。n 阶蛇形矩阵由前 n2 个正整数顺时针从外到内盘绕而成。

例如四阶具有如下形式：

1  2  3  4
12 13 14 5
11 16 15 6
10 9  8  7

五阶（奇数阶数）在中心位置略有不同：

1  2  3  4  5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

由于这种盘绕的方式过分诡异，无法简单的用数学语言表示。所以无聊又过分的出题人想让你算出这个矩阵每一行的和。

Input

输入一个整数 n (1≤n≤200 000)。

Output

输出 n 行 n 个整数，依次为每一行的和。

Examples

input

4

output

10
44
48
34

input

5

output

15
76
91
88
55

input

1

output

1

 

【代码】：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200005;
ll a[N];
int main()
{
    int n;
    cin>>n;
    ll l=1,r=n,f=n,s=0;
    a[1]=(l+r)*f/2;
    a[n]=a[1]+(f-1)*2*f;
    for(int i=2;i<=(n+1)/2;i++)
    {
        s+=r;
        l+=4*f-4,f=f-2,r=l+f-1;
        s+=l;
        a[i]=s+(l+r)*f/2;
        a[n-i+1]=a[i]+(f-1)*2*f;
    }
    for(int i=1;i<=n;i++)
        cout<<a[i]<<"
";
}