OI题库

【背景】

    小白在一个由n条横街，m条纵街的地方逛街。现在他饿了，想去买小吃。已知小吃街在第n条横街上，且每个街区有ai家小吃店。小白站在这个地方的左上角，为了早点买到小吃，他只向下和向右走。

【问题描述】

    在这n*m的地方，从左上角，只向下和向右走到第n行的某一段的ai中任意一点，求有多少种不同的方案。同一家店不同路线 和 同一路线不同店均视为不同的方案。

【输入文件】

第一行有二个整数n,m表示n行m列。
接下来m-1行，每行一个数ai表示第n行的每个街区的小吃店数量。

【输出文件】

方案总数。

 

【输入样例】

 

4 5
2
1
0
1

 

【输出样例】

26

26= 2*1 + 1*4 + 0*10 + 1*20

对于 30%数据, 0<=n,m<=10;ai=1
对于100%数据, 0<=n,m<=1,000
对于 100%数据，0<=ai<=1000