National Contest for Private Universities (NCPU), 2019 E. Generalized Pascal's Triangle

本文主要是介绍National Contest for Private Universities (NCPU), 2019 E. Generalized Pascal's Triangle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

编辑代码

2000ms
262144K

Generalized Pascal's Triangle

Pascal's triangle is a triangular array in which each number can be calculated by the sum of the two numbers directly above that number as shown in Figure 1. One of its prominent applications is to determine the coefficients which arise in binomial expansion (or binomial theorem), say the coefficients of $x+y)^n$ . Figure 1 also illustrates how to derive the elements layer by layer and shows that layer $k$ gives the coefficients of the expansion of $x+y)^k$ . We now want to generalize Pascal's triangle in higher dimension and consider the three-dimensional version. This three-dimensional version can be associated with the coefficients of the trinomial expansion, $x+y+z)^n$ , and its shape is a tetrahedron as shown in Figure 2(a) instead of a triangle. Figure 2(b)-(e) present the elements on layer 0, 1, 2, 3, and 4 (center) as well as demonstrate the relation between layer $i$ and layer $i + 1$ (right). The element on layer $i$ can be derived from two or three elements on layer $i - 1$ . This is the same as the coefficients in the expansion of trinomial $x+y+z)^i$ (on layer $i$ ) that can be calculated from the coefficients of $x+y+z)^{i-1}$ (on layer $i - 1$ ) with the sum of two or three numbers. Now, given an integer $n$ as the layer number, please list all the elements on layer $n$ in a triangular array.

Figure 1. Pascal's triangle

Figure 2. Three-dimensional version of Pascal's triangle: (a) The shape and (b)-(e) presenting the elements on layer $0, 1, 2, 3,$ and $4$ (center) as well as demonstrating the relation between layer $i$ and layer $i + 1$ (right) with associated trinomial expansion

Input Format

The input contains several test cases and is terminated by End-Of-File (EOF). Each test case is an integer $n$ .

Output Format

For each test case, the output is like a triangular array and shall be denoted in $n + 1$ lines depending on the input $n$ . The first line has one element (as the first coefficient in the expansion of $x+y+z)^n$ ) and the second line has two elements and etc. The last line has $n + 1$ elements that are the coefficients of the binomial expansion of $x+y)^n$ . The first column of the output array thus has $n + 1$ elements and those elements are also the coefficients of the binomial expansion of $x+y)^n$ . In each line of the output, all elements are separated by space key as delimiter.

Technical Specification

$0 \leq n \leq 20$

样例输入复制

2
3
4

样例输出复制

杨辉三角变形，杨辉三角是从上往下推这个是每个点也对上面有影响。数据量也不是很大直接滚动数组暴力了。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<map>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int INF = 0x3f3f3f3f;
int i,j,k;
int n;
const int N=21;
ll ans[N]= {1, 1};
long long v[2][60][60];
int main()
{while(~scanf("%d", &n)){memset(v,0,sizeof(v));v[0][1][1]=1;for(int k=1;k<=n;k++)for(int i=1;i<=k+1;i++){for(int j=1;j<=i;j++){v[k%2][i][j]=v[(k+1)%2][i][j]+v[(k+1)%2][i-1][j]+v[(k+1)%2][i-1][j-1];}}for(int i=1;i<=n+1;i++){for(int j=1;j<=i;j++){cout<<v[(n)%2][i][j];if(j<i)cout<<' ';}cout<<endl;}}return 0;
}

这篇关于National Contest for Private Universities (NCPU), 2019 E. Generalized Pascal's Triangle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！