当前位置：首页 > news >正文

打卡信奥刷题（2950）用C++实现信奥题 P5879 放棋子

news 2026/5/12 4:18:20

P5879 放棋子

题目描述

小虎刚刚上了幼儿园，老师让他做一个家庭作业：首先画333行格子，第一行有三个格子，第二行有222个格子，第三行有111个格子。每行的格子从左到右可以放棋子，但要求除第一行外，每行放的棋子数不能超过上一行的棋子。第一行的棋子数不能为000，但剩下行可以为空。玩了一会儿，小虎对哥哥大虎说：”这个作业有很多种摆放法，我想找到，但我不知道有多少种方案，你能帮助我吗？”

大虎是学校信息学集训队的，立刻想到用计算机来解决这个问题，并很快有了解答：131313。

第二天他把问题拿到学校，并说如果第一行有NNN个格子，第二行有N−1N-1N−1个格子，……，第NNN行有111个格子，怎么办？现在请你一块来帮助他解决这个难题。

输入格式

仅一行，一个正整数NNN。

输出格式

一行，方案总数。

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

样例 1 说明：N=2N=2N=2时，有如下444种摆放棋子法（*表示棋子，_表示空格）：

方案数	1	2	3	4
第一行	`*_`	`**`	`*_`	`**`
第二行	`_`	`_`	`*`	`*`

对于30%30\%30%数据：1≤N≤121\le N\le 121≤N≤12。

对于50%50\%50%数据：1≤N≤301\le N\le 301≤N≤30。

对于100%100\%100%数据：1≤N≤1001\le N\le 1001≤N≤100。

C++实现

#include<bits/stdc++.h>#defineFor(i,a,b)for(registerinti=(a);i<=(b);++i)#defineRep(i,a,b)for(registerinti=(a);i>=(b);--i)usingnamespacestd;constintmaxn=110;inlinevoidwrite(intx){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+48);}intn;intM=1,f[maxn][maxn][2],ans[2];intmain(){cin>>n;For(i,1,n)f[i][0][0]=1;For(i,1,30)M*=10;//构造一个30位的取模数，方便压位For(i,1,n)For(j,1,i){f[i][j][0]=(f[i][j-1][0]+f[i-1][j][0])%M;//压位，状方在前文已经讲过了f[i][j][1]=f[i][j-1][1]+f[i-1][j][1]+(f[i][j-1][0]+f[i-1][j][0])/M;}For(i,1,n)ans[0]+=f[n][i][0];ans[1]=ans[0]/M;//处理进位（很容易写错）ans[0]%=M;For(i,1,n)ans[1]+=f[n][i][1];if(ans[1]!=0){write(ans[1]);if(ans[0]<=M/10)cout<<0;//用一个比较讨巧的方法处理首位是0的情况}write(ans[0]);cout<<endl;//可省return0;}