文档章节

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

o
 osc_x4h57ch8
发布于 2018/04/24 11:03
字数 1023
阅读 0
收藏 0
ruo

精选30+云产品,助力企业轻松上云!>>>

2655: calc

Time Limit: 30 Sec  Memory Limit: 512 MB
Submit: 428  Solved: 246
[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

Source

[ Submit][ Status][ Discuss]

https://blog.csdn.net/qq_20669971/article/details/52790835

先列出DP方程,f[i][j]表示i个元素选j个进排列的总贡献,则f[i][j]=f[i-1][j-1]*i*j+f[i-1][j]。(这里也可以把n!提出来)

直接DP肯定不行,然后我们可以发现f[i][j]实际上是关于i的高次多项式,现在要确定是几次多项式。

第一种方法:f[i][i]=(i!)^2,根据递推式求得f[i][j]是2j次的。

https://www.cnblogs.com/xiao-ju-ruo-xjr/p/8510924.html

第二种方法:打表发现系数中i的次数和i本身的次数都为j。

https://blog.csdn.net/ez_yww/article/details/77221338

所以确定是2j次的(当然如果不想确定就多放几次也没关系)

 

这样我们可以用拉格朗日插值法先求出2n个点的f[x_i][n],拟合出多项式后将A代入即可(直接现场代入就好)

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define rep(i,l,r) for (int i=l; i<=r; i++)
 4 typedef long long ll;
 5 using namespace std;
 6 
 7 const int N=510;
 8 int f[N<<1][N],x,n,mod,ans,m;
 9 
10 int inv(int a){
11     int res=1,b=mod-2;
12     for (; b; a=1ll*a*a%mod,b>>=1)
13         if (b & 1) res=1ll*res*a%mod;
14     return res;
15 }
16 
17 int main(){
18     freopen("bzoj2655.in","r",stdin);
19     freopen("bzoj2655.out","w",stdout);
20     scanf("%d%d%d",&x,&n,&mod); f[0][0]=1; m=2*n+1;
21     rep(i,1,m) { f[i][0]=1; rep(j,1,n) f[i][j]=(f[i-1][j]+1ll*i*f[i-1][j-1])%mod; }
22     rep(i,1,m){
23         int a=f[i][n],b=1;
24         rep(j,1,m) if (i!=j) a=1ll*a*(x-j)%mod,b=1ll*b*(i-j)%mod;
25         a=1ll*a*inv(b)%mod; ans=(ans+a)%mod;
26     }
27     rep(i,1,n) ans=1ll*ans*i%mod;
28     printf("%d\n",(ans+mod)%mod);
29     return 0;
30 }

可以O(m)插值,预处理一些东西就好(不过瓶颈在于DP所以无所谓)

边界考虑清楚。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define rep(i,l,r) for (int i=l; i<=r; i++)
 4 typedef long long ll;
 5 using namespace std;
 6 
 7 const int N=510;
 8 int x,n,mod,ans,m,f[N<<1][N],pre[N<<1],suf[N<<1],fac[N<<1],fin[N<<1];
 9 
10 int inv(int a){
11     int res=1,b=mod-2;
12     for (; b; a=1ll*a*a%mod,b>>=1)
13         if (b & 1) res=1ll*res*a%mod;
14     return res;
15 }
16 
17 int main(){
18     freopen("bzoj2655.in","r",stdin);
19     freopen("bzoj2655.out","w",stdout);
20     scanf("%d%d%d",&x,&n,&mod); m=2*n+1;
21     rep(i,0,m) f[i][0]=1;
22     rep(i,1,m) rep(j,1,n) f[i][j]=(f[i-1][j]+1ll*i*f[i-1][j-1])%mod;
23     pre[0]=1; rep(i,1,m) pre[i]=1ll*pre[i-1]*(x-i)%mod;//(x-1)*(x-2)*...*(x-i)
24     suf[0]=(x-m)%mod; rep(i,1,m) suf[i]=1ll*suf[i-1]*(x-m+i)%mod;//(x-m)*(x-m+1)*...(x-m+i)
25     fac[0]=1; rep(i,1,m) fac[i]=1ll*fac[i-1]*i%mod;//1*2*...*i
26     fin[m]=inv(fac[m]); for (int i=m-1; ~i; i--) fin[i]=1ll*fin[i+1]*(i+1)%mod;//1/(1*2*...*i)
27     rep(i,1,m){
28         int a=1ll*f[i][n]*pre[i-1]%mod*((i==m)?1:suf[m-i-1])%mod;
29         int b=1ll*fin[i-1]%mod*fin[m-i]*(((m-i)&1)?-1:1)%mod;
30         ans=(ans+1ll*a*b)%mod;
31     }
32     rep(i,1,n) ans=1ll*ans*i%mod;
33     printf("%d\n",(ans+mod)%mod);
34     return 0;
35 }

 以及另一道用拉格朗日插值法简化的题目:[BZOJ4559][JLOI2016]成绩比较

http://www.cnblogs.com/nbwzyzngyl/p/8394921.html

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

在Bash脚本中,如果发生某种情况,如何退出整个脚本?

问题: I'm writing a script in Bash to test some code. 我正在Bash中编写脚本来测试一些代码。 However, it seems silly to run the tests if compiling the code fails in the first pl......

技术盛宴
17分钟前
11
0
Windows安装Python+OpenCV

1、更新PyCharm中pip来源,使用清华和阿里云:https://pypi.tuna.tsinghua.edu.cn/simple/ http://mirrors.aliyun.com/pypi/simple/ 2、PyCharm查看已安装packets,添加新的安装包,从pip云端...

极客行
40分钟前
17
0
tomcat8配置虚拟目录,实现一个tomcat运行两个项目, tomcat配置URL不区分大小写

<?xml version="1.0" encoding="UTF-8"?><!-- Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements. See the NOTICE file distri......

青峰Jun19er
46分钟前
19
0
HBase和MySQL存储方式的差别?或者说是,行存储和列存储的区别?

HBase借鉴列存储的思想,但是最底层依然是依靠键值对来存储数据,HBase为非关系型数据库 而MySQL则是行存储,MySQL为关系型数据库 写过程 行存储因为数据是连续的,所以只需要进行追加即可;...

其乐m
50分钟前
25
0
一个老程序员在互联网寒冬下的感悟

1. 你千万不要认为学习技术就可以换来稳定的生活和高的薪水待遇,你更不要认为那些从事市场开发,跑腿的人,没有前途。 不清楚你是不是知道,咱们中国有相当大的一部分软件公司,他们的软件开...

北柠Java
54分钟前
39
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部