递推专练2

从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？最终答案mod12345。
读入一个数N。1<=N<=1000。
input:2 output:7
分析：
这个题一开始就把我迷惑了。最后我画出了一个图才发现怎么实现。
这张图，假设原点为a[i-1]，我们要去的这个点为a[i+1]，那么重点就来了。这题怎么用递推求出来呢？
我们看，要走到a[i+1]，我们必须走过a[i]。要走过a[i]，必须走a[i-1]。
这样我们递推的雏形就出来了。
不过我们还需要考虑一件事情，这个就是我没有考虑到的，最后经过我旁边的神犇LYL的开导，观察这个图像，要走到a[i+1]其实可以走两条路，从左下走或者从右上走。那么我们算的路程方法数必须乘2！！！

最后我们可以得出
a [ i ] = 2 ∗ a [ i − 1 ] a[i]=2 * a[i-1] a[i]=2∗a[i−1]
但是这个也不是最完美的。但是我们要想想，如果左右走的话，有可能重复，比如上图我们如果从a[i-1]走到a[i]，再从a[i]走回a[i-1]，那么就完全没意义了。所以我们必须想，只有高度改变了才能左右走，如果有这个前提，那么就好办了！
也就是a[i-2]向上1步形成的节点。那么我们的递推式就出来了！
a [ i ] = 2 ∗ a [ i − 1 ] + a [ i − 2 ] a[i]=2 * a[i-1] +a[i-2] a[i]=2∗a[i−1]+a[i−2]
好的，真是完美。
At last，别忘了mod 12345，特别是别忘了在算的过程中mod，因为在算的时候有可能数据就数据已经爆炸了，导致交上去爆0。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[19260817];
int main(){
//	freopen("problem1.in","r",stdin);
//	freopen("problem1.out","w",stdout);
	cin>>n;
	a[0]=1,a[1]=3;
	for(int i=2;i<=n;i++){
		a[i]=(2*a[i-1]+a[i-2])%12345 //独特共鸣，奇妙深刻。
	}
	cout<<a[n]<<endl;
	return 0;
}

分数字

现有N件不可区分的物品，将它们分成10份，要求每份在1~3件之间，问有多少种方案，并按字典序输出所有方案。
输入格式 一个整数表示N<=10000
输出格式 第一行一个M表示方案数。接下来M行每行10个整数表示一种方案。
input:
11
output:
10
1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 2 1 1 1
1 1 1 1 1 2 1 1 1 1
1 1 1 1 2 1 1 1 1 1
1 1 1 2 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1 1
2 1 1 1 1 1 1 1 1 1

做法（1）十重循环枚举出答案。
因为数据点不大，所以这题用十重完全能A，不过不建议写我这种写法
主要流程是第一个十重循环控制求出所有的方案数，因为是1-3种，最大是3，那么我们选10个变量，相加，如果正好等于这n种物品，方案数+1。
第二个十重循环遍历一遍就可以得出所有可能解了。至于字典序，不必管他。

#include<bits/stdc++.h>
using namespace std;
int x[11][10010];
int n,ans=0;
int main()
{
	//freopen("allot.in","r",stdin);
	//freopen("allot.out","w",stdout);
	cin>>n;
	for(int a=1;a<=3;a++)
		for(int aa=1;aa<=3;aa++)
			for(int aaa=1;aaa<=3;aaa++)
				for(int aaaa=1;aaaa<=3;aaaa++)
					for(int aaaaa=1;aaaaa<=3;aaaaa++)
						for(int aaaaaa=1;aaaaaa<=3;aaaaaa++)
							for(int aaaaaaa=1;aaaaaaa<=3;aaaaaaa++)
								for(int aaaaaaaa=1;aaaaaaaa<=3;aaaaaaaa++)
									for(int aaaaaaaaa=1;aaaaaaaaa<=3;aaaaaaaaa++)
										for(int aaaaaaaaaa=1;aaaaaaaaaa<=3;aaaaaaaaaa++)

											if(a+aa+aaa+aaaa+aaaaa+aaaaaa+aaaaaaa+aaaaaaaa+aaaaaaaaa+aaaaaaaaaa==n){
												ans++;
											}
	cout<<ans<<endl;
	for(int a=1;a<=3;a++)
		for(int aa=1;aa<=3;aa++)
			for(int aaa=1;aaa<=3;aaa++)
				for(int aaaa=1;aaaa<=3;aaaa++)
					for(int aaaaa=1;aaaaa<=3;aaaaa++)
						for(int aaaaaa=1;aaaaaa<=3;aaaaaa++)
							for(int aaaaaaa=1;aaaaaaa<=3;aaaaaaa++)
								for(int aaaaaaaa=1;aaaaaaaa<=3;aaaaaaaa++)
									for(int aaaaaaaaa=1;aaaaaaaaa<=3;aaaaaaaaa++)
										for(int aaaaaaaaaa=1;aaaaaaaaaa<=3;aaaaaaaaaa++)
											if(a+aa+aaa+aaaa+aaaaa+aaaaaa+aaaaaaa+aaaaaaaa+aaaaaaaaa+aaaaaaaaaa==n)
												cout<<a<<' '<<aa<<' '<<aaa<<' '<<aaaa<<' '<<aaaaa<<' '<<aaaaaa<<' '<<aaaaaaa<<' '<<aaaaaaaa<<' '<<aaaaaaaaa<<' '<<aaaaaaaaaa<<endl;
	return 0;
 } 

做法（2） 通过递归Dfs的方法完成
首先确定什么情况是都不用算的。
当方案数n<10或者>30的时候，一定所有方案都没有。这点从读题就可以读出来。
开一个dfs函数
首先将所给的数分成10份，然后写边界条件。
我们发现边界条件是x==0，也就是说所有数字分完的时候，则总和++。接着输出各个元素。
然后考虑递归的问题，我们设一个i可以从1-3遍历，如果x<i的话，那么就不够装了，我们跳过。
如果够装，就装进去，最后回溯

#include<bits/stdc++.h>
using namespace std;
int ans[100050],a[5000][5000],tet=0,sum=0;
void dfs(int x,int time)
{
	if(tet==10)
	{
		if(x==0)
		{
			sum++;
			if(time==2)
			{
				for(long long i=1;i<tet;i++)
				{
					cout<<ans[i]<<" ";
				}
				cout<<ans[tet]<<endl;
			}
			return;
		}
		return;
	}
	for(long long i=1;i<=3;i++)
	{
		if(x<i)
		{
			return;
		}
		ans[++tet]=i;
		dfs(x-i,time);
		ans[tet]=0;
		tet--; 
	}
}
int main()
{
	freopen("allot.in","r",stdin);
	freopen("allot.out","w",stdout);
	long long m;
	cin>>m;
	if(m>30 || m<10)
	{
		cout<<0<<endl;
		return 0;
	}
	else
	{
		dfs(m,1);
		cout<<sum<<endl;
		dfs(m,2);
	}
	return 0;
}