问题标题: 酷町堂：3409 杨辉三角加强版

3409   杨辉三角加强版经验值：2000

题目描述 Description

给定一个正整数n，请输出杨辉三角形前n行的偶数个数对1000003取模后的结果。

输入描述 Input Description

一个数n

输出描述 Output Description

结果

样例输入 Sample Input

6

样例输出 Sample Output

6

数据范围及提示 Data Size & Hint

对于30%的数据，n<=4000

对于70%的数据，n<=4*10^9

对于100%的数据，n<=10^15

杨辉三角形的前七行：

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

要不是因为这是每日一题我才不做这个破题呢...

下面有请RE30的代码出场：

#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    int n,cnt=0;
    cin>>n;
    const int m = 2 * n-1;
    int a[n + 1][m] ;
    for (int i = 0; i < n; i++){
        a[i][n - i- 1] = 1;
        a[i][n + i -1] = 1;
    }
    for (int i = 2; i < n; i++){
        for (int j = n - i + 1; j < n-2+i; j = j + 2)
            a[i][j] = a[i - 1][j - 1] + a[i - 1][j + 1];
    }
    int p;
    for (int i = 0; i < n; i++){
        p = 1;
        for (int j = n - i - 1; p < i + 2; j = j + 2)
        {
            if(a[i][j]%2==0)cnt++;
            cnt%=1000003;
            //cout << arr[i][j] << " ";
            p = p + 1;
        }
        //cout << endl;
    }
    cout<<cnt;
    return 0;
}

众所周知3409这道题木有人问过，但绝对会有人一边水贴一边说我在刷分