注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2655]calc(拉格朗日插值)  

2015-05-20 07:53:22|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2655: calc

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 91  Solved: 66
[Submit][Status][Discuss]

Description

一个序列a1,...,an是合法的,当且仅当:
长度为给定的n。
a1,...,an都是[1,A]中的整数。
a1,...,an互不相等。
一个序列的值定义为它里面所有数的乘积,即a1a2...an。
求所有不同合法序列的值的和。
两个序列不同当且仅当他们任意一位不一样。
输出答案对一个数mod取余的结果。

Input

一行3个数,A,n,mod。意义为上面所说的。

Output

一行结果。

Sample Input

9 7 10007

Sample Output

3611

HINT

数据规模和约定
0:A<=10,n<=10。
1..3:A<=1000,n<=20.
4..9:A<=10^9,n<=20
10..19:A<=10^9,n<=500。

全部:mod<=10^9,并且mod为素数,mod>A>n+1

Solution

当n一样时,记f_n(x)为答案,可以发现{f_n(1),f_n(2),...,f_n(n-1)}均为0,而其它的数构成了一个最高次项为x^2*n的多项式。
于是比如当n=500的时候,暴力求出f(501)~f(1001),然后拉格朗日插值来拟合多项式,最后直接把A的值代进去就好了。

Code

/**************************************************************
    Problem: 2655
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:568 ms
    Memory:6840 kb
****************************************************************/
 
#include<cstdio>
typedef long long ll;
int n,m,i,j,k,p,tot;ll tmp,f[1510][510],fac[510],x[1010],y[1010],a,b,ans;
ll power(ll t,int k){
    for(tmp=1;k;k>>=1,t=t*t%p)if(k&1)tmp=tmp*t%p;
    return tmp;
}
ll Lagrange(){
    for(a=1,i=0;i<tot;i++)a=a*(m-x[i]+p)%p;
    for(i=0;i<tot;ans=(ans+a*power(b,p-2)%p*y[i])%p,i++)
    for(b=(m-x[i]+p)%p,j=0;j<tot;j++)if(i!=j)b=b*(x[i]-x[j]+p)%p;
    return ans;
}
int main(){
    scanf("%d%d%d",&m,&n,&p);f[0][0]=1;
    for(fac[0]=i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
    for(i=1;i<=n*3+5;i++)
    for(f[i][0]=1,j=1;j<=n+5;j++)
    f[i][j]=(f[i-1][j]+i*f[i-1][j-1])%p;
    for(i=1;tot<=n*2+1;i++)if(f[i][n]&&i!=m)x[tot]=i,y[tot]=f[i][n],tot++;
    printf("%lld\n",Lagrange()*fac[n]%p);
}
  评论这张
 
阅读(609)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018