火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。
从第3站起（包括第3站）上、下车的人数有一定规律：上车的人数都是前两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。
现给出的条件是：共有N个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。
试问x站开出时车上的人数是多少？
Input有多组测试数据。
每组测试数据仅包含一行，每行包括四个整数，a，n，m和x。
0<= a <= 10
3<= n <= 30
1 <= x < n
0 <= m <= 2^31-1
Output对于每组测试数据，输出一行，包括一个整数，即从x站开出时车上的人数。Sample Input5 7 32 4Sample Output13
【分析】：
1.枚举第二站上下车的人数，根据题目给出的递推关系判断是否正确。递推关系题目描述得很清晰，数据规模也完全没有问题。
记第i站车上人数为f[i],上车人数为up[i],下车人数为down[i]
第一站人数为a则f[1]=a,up[1]=a,down[1]=0;
枚举第二站上下车的人k(0<=k<=m)
up[2]=down[2]=k;f[2]=f[1]+up[2]-down[2]=a;
第i站(3<=i<n)：
up[i]=up[i-1]+up[i-2];
down[i]=up[i-1];
f[i]=f[i-1]+up[i]-down[i]
=f[i-1]+up[i-2];
由此我们第i站车上的乘客和down并没有关系
所以我们只要递推up和f
如果f[n-1]=m的话就得到了答案
————————————————————————————————————————————————————————
注意由于题目没有给出数据范围，不要把整个f和up开出来，直接使用临时变量递推
实际数据范围只要开到100就行
(不加优化即可过这道题，不过还是讲讲优化)
优化1
由于f是单调递增的可以二分查找
优化2
递推可以试试矩阵快速幂
【代码】：
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define mod 1000000
using namespace std;
long long up[],down[],s[];
int main()
{
long long a,n,m,x,flag,i,j;
while(cin>>a>>n>>m>>x)
{
memset(s,,sizeof(s));
up[]=a;
flag=;
down[]=;
s[]=a;
for(i=;i<=m;i++)
{
up[]=i;
down[]=i;
s[]=s[];
for(j=;j<n;j++)
{
up[j]=up[j-]+up[j-];
down[j]=up[j-];
s[j]=s[j-]+up[j-];
}
if(s[n-]==m)
{
flag=;
printf("%lld\n",s[x]);
break;
}
}
}
return ;
}
枚举+递推
#include <bits/stdc++.h>
using namespace std;
int a,n,m,x;
int u[],c[];
int main()
{
cin>>a>>n>>m>>x;
u[]=a;
c[]=a;
c[]=a;
for(int k=;k<=m;k++)
{
u[]=k;
for(int i=;i<n;i++)
{
u[i]=u[i-]+u[i-];
c[i]=c[i-]+u[i-];
}
if(c[n-]==m)
{
cout<<c[x];
return ;
}
}
}
化简版
//数论
/*
* 第几站 上车 下车 车上人数
* 1 a1 0 a1
* 2 a2 a2 a1
* 3 a1+a2 a2 a1+a1
* 4 a1+a2+a2 a1+a2 a1+a1+a2
* 5 a1+a2+a1+a2+a2 a1+a2+a2 a1+a1+a2+a1+a2
* . . . .
* . . . .
* . . . .
* 到最后一站的人数就是m ，全部下完
* 思路，只要统计出a1个数和a2的个数就能求出a2，其中a1已经给出，m的数量就是n-1车站的开车的人数
* a2=(m-a1*a1的个数)/a2的个数
*/
#include<cstdio>
#include<cstring>
using namespace std;
int A[];
int B[];
void f(){
A[]=,A[]=,A[]=;
A[]=,A[]=;
for(int i=;i<=;i++)
A[i]=A[i-]+A[i-]-;
}
void ff(){
B[]=,B[]=,B[]=;
B[]=,B[]=;
for(int i=;i<=;i++)
B[i]=B[i-]+B[i-]+;
}
int main()
{
int a,n,m,x;
f();
ff();
while(~scanf("%d%d%d%d",&a,&n,&m,&x)){
int b[];
memset(b,,sizeof(b));
b[]=a;
b[]=a;
b[]=*a;
int xx=(m-A[n-]*a)/B[n-];
for(int i=;i<=;i++)
b[i]=A[i]*a+B[i]*xx;
printf("%d\n",b[x]);
}
return ;
}
学长出品，必属精品