火车从始发站（称为第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
      
       #define INF 0x3f3f3f3f#define mod 1000000using namespace std;long long up[10000],down[10000],s[10000];int main(){    long long a,n,m,x,flag,i,j;    while(cin>>a>>n>>m>>x)    {        memset(s,0,sizeof(s));        up[1]=a;        flag=0;        down[1]=0;        s[1]=a;        for(i=0;i<=m;i++)        {            up[2]=i;            down[2]=i;            s[2]=s[1];            for(j=3;j
      

 

#include 
      
       using namespace std;int a,n,m,x; int u[100005],c[100005];int main(){        cin>>a>>n>>m>>x;        u[1]=a;        c[1]=a;        c[2]=a;        for(int k=0;k<=m;k++)        {                u[2]=k;                for(int i=3;i
      

 

//数论/*  * 第几站   上车        下车         车上人数  * 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
      
       #include
       
        using namespace std;int A[35];int B[35];void f(){    A[1]=1,A[2]=1,A[3]=1;    A[4]=2,A[5]=3;    for(int i=6;i<=30;i++)        A[i]=A[i-1]+A[i-2]-1;}void ff(){    B[1]=1,B[2]=1,B[3]=1;    B[4]=1,B[5]=2;    for(int i=6;i<=30;i++)        B[i]=B[i-1]+B[i-2]+1;}int main(){   int a,n,m,x;   f();   ff();   while(~scanf("%d%d%d%d",&a,&n,&m,&x)){    int b[35];    memset(b,0,sizeof(b));    b[1]=a;    b[2]=a;    b[3]=2*a;    int xx=(m-A[n-1]*a)/B[n-1];    for(int i=4;i<=30;i++)        b[i]=A[i]*a+B[i]*xx;    printf("%d\n",b[x]);   }   return 0;}