UVALive 6472 Powers of Pascal

标题手段:

他给了一个无限Pascal阵,定义了powers,然后询问power为P的pascal矩阵里面的第R行C列的元素是多少。

最開始读错题意了...然后 就成了一个神得不得了的题了。后来请教的别人。

感觉能够用矩阵高速幂做。

然后,不用高速幂的话,你会惊奇的发现,变成了找规律的题了...

答案成了 comb(i,j) * P^(i-j)

对于comb(i,j),利用组合数性质,能够得到,当j>i-j 的时候 j=i-j;

由于题目说答案不会爆long long  所以能够预处理,大概56左右,后发现50也行

组合数公式 Comb(i,j)=Comb(i-1,j)+Comb(i-1,j-1);

Ps:写这个是为了提醒自己....有时候打表找规律也是一种做一些数学有关的题的手段,当时实在不知道怎么做了时。

代码例如以下。再次感谢xxx

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; const int maxn=100000;
typedef long long LL;
LL C[maxn+2][52];
LL kk,k,p,r,c; void init()
{ for(int i=0;i<=maxn;i++) C[i][0]=1;
for(int i=1;i<=maxn;i++)
for(int j=1;j<=min(i,50);j++)
C[i][j]=C[i-1][j]+C[i-1][j-1];
}
int main()
{
init();
//cout<<C[3][1]<<endl;
scanf("%lld",&k);
while(k--)
{
scanf("%lld%lld%lld%lld",&kk,&p,&r,&c);
LL ans=1;
for(int i=1;i<=(r-c);i++)
ans*=p;
if(c>r/2) c=r-c;
ans*=C[r][c];
printf("%lld %lld\n",kk,ans);
}
return 0;
}

版权声明:本文博客原创文章,博客,未经同意,不得转载。

上一篇:Matlab 矩阵【Mark】


下一篇:MySQL 高性能优化实战总结