步步高升【非递归】

发布于:2021-10-17 01:36:18

> Description
春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位,看到一盆叫做“步步高升”的盆竹。“步步高升,步步高升……”学*就是要一步一步来,不能急,要打好基础。在稳固的基础上才谈得上步步高升!TENSHI若有所思。她看到这盆东西好意头,于是想买下。谁知一问价钱,“不贵不贵,才2XXRMB。”TENSHI差点没昏倒,囊中羞涩嘛。但是TENSHI还是很想买下来,于是她就在一旁观察。观察了一段时间,她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi元,那么他第i+1次报的价格为Wi-A或Wi -B。到了最后,TENSHI以Z元成交,高高兴兴的回家去了。
  求TENSHI把盆竹的价格由W1元杀到Z元的方法总数。



> Input
第一行有两个正整数W1和Z。第二行有两个正整数A和B。它们满足条件:
10 ≤ W1 ≤106,1 ≤ Z ≤ 106 ,Z < W1
2 ≤ A 、B ≤ 10000,A≠B



> Output
方法总数
注意:结果不超过MAXLONGINT



> Sample Input
样例1
256 88
5 9
样例2
100 10
13 23



> Sample Output
样例1
3889832
样例2



> 做题思路
首先知道:ax+by=w-z(x/y为a/b减价的次数)。
如何实现:用一个类似于鸡兔同笼的for语句。当条件实现的时候,就用ans累加一组有重复元素的全排列P(x,y)。


PS:有重复元素的全排列的个数=(x+y)!/x!y!。为了简化代码,可以先简化公式。简化后的公式??(x+y)!/x!y! = x!(x+1)(x+2)…(x+y)/x!y! = **(x+1)(x+2)…*(x+y)/y!**。



> 代码


#include
#include
using namespace std;
long long w,z,a,b,ans=0;
int n,m;

long long ooo(int n1,int m1)
{
double aka=1;
//double为了每次的商可能不是整数
for(int i=1;i<=m1;i++)
aka=aka*(n1+i)/i;
return ((long long)aka);
}

void lil()
{
int s=w-z; //ax+by的总和
for(int i=1;i<=s/a;i++)
{
int y=s-a*i; //此时的by总数
if(y%b==0) //当ax+by成立
{
n=i; m=y/b; //n为x,m为y
ans+=ooo(n,m); //调用后累加
}
}
}

int main()
{
scanf("%I64d%I64d%I64d%I64d",&w,&z,&a,&b);
lil();
printf("%I64d",ans);
return 0;
}

相关推荐

最新更新

猜你喜欢