// 1002 树屋阶梯.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
/*
http://oj.daimayuan.top/course/22/problem/1107
暑假期间，小龙报名了一个模拟野外生存作战训练班来锻炼体魄，训练的第一个晚上，教官就给他们出了个难题。
由于地上露营湿气重，必须选择在高处的树屋露营。小龙分配的树屋建立在一颗高度为 N+1
尺（N为正整数）的大树上，正当他发愁怎么爬上去的时候，发现旁边堆满了一些空心四方钢材，经过观察和测量，
这些钢材截面的宽和高大小不一，但都是 1尺的整数倍，教官命令队员们每人选取 N个空心钢材来搭建一个总高度为 N尺的阶梯来进入树屋，
该阶梯每一步台阶的高度为 1尺，宽度也为 1尺。
如果这些钢材有各种尺寸，且每种尺寸数量充足，那么小龙可以有多少种搭建方法？
以树屋高度为 4尺、阶梯高度 N=3尺为例，小龙一共有如图所示的 5种搭建方法:
输入格式
一个正整数 N（1≤N≤500），表示阶梯的高度。
输出格式
一个正整数，表示搭建方法的个数。（注：搭建方法个数可能很大。）
样例输入
3
样例输出
5
提示
对于100%
的数据，1≤N≤500。
*/
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 2010;
int primes[N], sum[N], cnt;
bool st[N];
int n;
void init() {
for (int i = 2; i <= N - 1; i++) {
if (!st[i]) primes[++cnt] = i;
for (int j = 1; i * primes[j] <= N - 1; j++) {
st[i * primes[j]] = true;
if (i % primes[j] == 0) break;
}
}
}
int get(int a, int p) {
int res = 0;
while (a) {
res += a / p;
a /= p;
}
return res;
}
vector<int> mul(vector<int> a, int b) {
vector<int> res;
int t = 0;
for (int i = 0; i < a.size()||t; i++) {
if (i < a.size()) t += a[i] * b;
res.push_back(t % 10);
t /= 10;
}
return res;
}
int main()
{
cin >> n;
init();
for (int i = 1; i <= cnt; i++)
sum[i] = get(2 * n, primes[i]) - 2 * get(n, primes[i]);
int c = n + 1;
for (int i = 1; i <= cnt; i++) {
while (c % primes[i] == 0) {
c /= primes[i];
sum[i]--;
if (c == 1) break;
}
}
vector<int> res;
res.push_back(1);
for (int i = 1; i <= cnt; i++) {
for (int j = 1; j <= sum[i]; j++) {
res = mul(res, primes[i]);
}
}
for (int i = res.size() - 1; i >= 0; i--)cout << res[i];
cout << endl;
return 0;
}
#include <cstdio>
#include <iostream>
#define maxn 120005
#define ll long long
using namespace std;
int n,g;
int a,b,fm[maxn],fz[maxn],ans[maxn*100];
int qpow(int a,int b){//快速幂
int res=1;
for(;b;b>>=1){
if(b&1)res=res*a;
a*=a;
}
return res;
}
//ans[0]存大整数的位数
void mul(int x){
int k=0;//向前一步的进位
for(int i=1;i<=ans[0];i++){
ans[i]*=x;
ans[i]+=k;
k=ans[i]/10;
ans[i]%=10;
}
while(k){
ans[++ans[0]]+=k;
k=ans[ans[0]]/10;
ans[ans[0]]%=10;
}
}
int main(){
scanf("%d",&n);
for(int i=2;i<=n;++i){
a=n+i;//(n+2)*(n+3)*...*(2n) 分子
for(int j=2;j*j<=a;j++){//质因数分解
while(a%j==0)fz[j]++,a/=j;
}
if(a>1) fz[a]++;
b=i;//1*2*3*...*n 分母
for(int j=2;j*j<=b;j++){
while(b%j==0)fm[j]++,b/=j;
}
if(b>1) fm[b]++;
}
ans[0]=ans[1]=1;
for(int i=2;i<=n*2;i++){
if(fz[i]==0) continue;
fz[i]=fz[i]-fm[i];
if(fz[i]==0) continue;
int x=qpow(i,fz[i]);
if(x!=1) mul(x);
}
for(int i=ans[0];i>=1;--i) printf("%d",ans[i]);//注意要倒序输出
return 0;
}
dp
#include<iostream>
#include<stdio.h>
using namespace std;
int f[550][500];//f[i][j]表示第i个数的第j位。
int len=1;
void add(int u)
{
for(int i=1;i<=len;i++)
f[u][i]=f[u-1][i]+f[u][i];
for(int i=1;i<=len;i++)
{
f[u][i+1]+=f[u][i]/10;
f[u][i]%=10;
}
if(f[u][len+1])len++;
}
int main()
{
int n,p;
cin>>n;
f[1][1]=1;
for(int i=2;i<=n+1;i++)
for(int j=1;j<=i;j++)
add(j);
for(int i=len;i>0;i--)
cout<<f[n][i];
}