BZOJ2655 calc(动态规划+拉格朗日插值法)

时间:2022-09-09 11:51:40

  考虑暴力dp:f[i][j]表示i个数值域1~j时的答案。考虑使其值域++,则有f[i][j]=f[i][j-1]+f[i-1][j-1]*i*j,边界f[i][i]=i!*i!。

  注意到值域很大,考虑能不能在这一维上优化。完全不会证地有f[i][j]是一个关于j的2i次多项式。那么dp出一部分后就可以直接拉格朗日插值求出多项式,代入即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 510
int n,m,P,f[N][N<<],fac[N],ans=;
int ksm(int a,int k)
{
if (k==) return ;
int tmp=ksm(a,k>>);
if (k&) return 1ll*tmp*tmp%P*a%P;
else return 1ll*tmp*tmp%P;
}
int inv(int x){return ksm(x,P-);}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj2655.in","r",stdin);
freopen("bzoj2655.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
m=read(),n=read(),P=read();
fac[]=;for (int i=;i<=n;i++) fac[i]=1ll*fac[i-]*i%P;
for (int i=;i<=n;i++)
{
f[i][i]=1ll*fac[i]*fac[i]%P;
for (int j=i+;j<=(n<<);j++)
f[i][j]=(f[i][j-]+1ll*f[i-][j-]*i%P*j%P)%P;
}
for (int i=;i<=(n<<);i++)
{
int w=f[n][i],v=;
for (int j=;j<=(n<<);j++)
if (i!=j) w=(1ll*w*(m-j+P)%P)%P,v=1ll*v*(i-j+P)%P;
ans=(ans+1ll*w*inv(v))%P;
}
cout<<ans;
return ;
}

BZOJ2655 calc(动态规划+拉格朗日插值法)的更多相关文章

  1. BZOJ2655 Calc - dp 拉格朗日插值法

    BZOJ2655 Calc 参考 题意: 给定n,m,mod,问在对mod取模的背景下,从[1,m]中选出n个数相乘可以得到的总和为多少. 思路: 首先可以发现dp方程 ,假定dp[m][n]表示从[ ...

  2. 【BZOJ】2655&colon; calc 动态规划&plus;拉格朗日插值

    [题意]一个序列$a_1,...,a_n$合法当且仅当它们都是[1,A]中的数字且互不相同,一个序列的价值定义为数字的乘积,求所有序列的价值和.n<=500,A<=10^9,n+1< ...

  3. BZOJ2655&colon; calc&lpar;dp 拉格朗日插值&rpar;

    题意 题目链接 Sol 首先不难想到一个dp 设\(f[i][j]\)表示选了\(i\)个严格递增的数最大的数为\(j\)的方案数 转移的时候判断一下最后一个位置是否是\(j\) \[f[i][j] ...

  4. &lbrack;BZOJ2655&rsqb;calc&lpar;拉格朗日插值法&plus;DP&rpar;

    2655: calc Time Limit: 30 Sec  Memory Limit: 512 MBSubmit: 428  Solved: 246[Submit][Status][Discuss] ...

  5. &lbrack;国家集训队&rsqb; calc&lpar;动规&plus;拉格朗日插值法&rpar;

    题目 P4463 [国家集训队] calc 集训队的题目真是做不动呀\(\%>\_<\%\) 朴素方程 设\(f_{i,j}\)为前\(i\)个数值域\([1,j]\),且序列递增的总贡献 ...

  6. bzoj千题计划269:bzoj2655&colon; calc &lpar;拉格朗日插值)

    http://www.lydsy.com/JudgeOnline/problem.php?id=2655 f[i][j] 表示[1,i]里选严格递增的j个数,序列值之和 那么ans=f[A][n] * ...

  7. Matlab数值计算示例: 牛顿插值法、LU分解法、拉格朗日插值法、牛顿插值法

    本文源于一次课题作业,部分自己写的,部分借用了网上的demo 牛顿迭代法(1) x=1:0.01:2; y=x.^3-x.^2+sin(x)-1; plot(x,y,'linewidth',2);gr ...

  8. 拉格朗日插值法——用Python进行数值计算

    插值法的伟大作用我就不说了.... 那么贴代码? 首先说一下下面几点: 1. 已有的数据样本被称之为 "插值节点" 2. 对于特定插值节点,它所对应的插值函数是必定存在且唯一的(关 ...

  9. CPP&amp&semi;MATLAB实现拉格朗日插值法

    开始学习MATLAB(R和Python先放一放...),老师推荐一本书,看完基础就是各种算法...首先是各种插值.先说拉格朗日插值法,这原理楼主完全不懂的,查的*,好久才看懂.那里讲的很详细,这 ...

随机推荐

  1. c&num;中两种不同的存储过程调用与比较

    存储过程简介 简单的说,存储过程是由一些SQL语句和控制语句组成的被封装起来的过程,它驻留在数据库中,可以被客户应用程序调用,也可以从另一个过程或触发器调用.它的参数可以被传递和返回.与应用程序中的函 ...

  2. 【转载】Pyqt QSplitter分割窗口

    转载来自: http://blog.sina.com.cn/s/blog_4b5039210100h3ih.html 分割窗口在应用程序中经常用到,它可以灵活分布窗口布局,经常用于类似文件资源管理器的 ...

  3. Binary Tree 分类: POJ 2015-06-12 20&colon;34 17人阅读 评论&lpar;0&rpar; 收藏

    Binary Tree Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 6355   Accepted: 2922 Descr ...

  4. JS计算字符串所占字节数

    最近项目有个需求要用js计算一串字符串写入到localStorage里所占的内存,众所周知的,js是使用Unicode编码的.而Unicode的实现有N种,其中用的最多的就是UTF-8和UTF-16. ...

  5. 接收Firfox RESTClient &num;Post请求

    什么是 RESTClient 请参考:http://www.blogjava.net/paulwong/archive/2014/04/19/412688.html 对接接口时经常会需要传个异步回调消 ...

  6. DIV&plus;CSS外部字体引用

    注意: 由于各个浏览器兼容问题大家还是少用这个,下面是具体的使用方法和效果截图: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN&qu ...

  7. liunx下NetworkManager导致网卡不能启动

    前几天在客户现场,配置一台系统为redhat 6.0的服务器,这台服务器是IBM x3755,系统是预装的.在把服务器的IP地址配置完成后,使用命令不能启动网卡.提示:弹出界面 eht0:错误:激活链 ...

  8. &period;Net程序员学用Oracle系列&lpar;26&rpar;:PLSQL 之类型、变量和结构

    1.类型 1.1.属性类型 1.2.记录类型 2.变量 2.1.变量类型 2.2.变量定义 2.3.变量赋值 3.结构 3.1.顺序结构 3.2.选择结构 3.3.循环结构 4.总结 1.类型 在&l ...

  9. JS键盘事件对象之keyCode、charCode、which属性对比

    先说一些有关键盘事件的事项:用js实现键盘记录,要关注浏览器的三种按键事件类型,即keydown,keypress和keyup,它们分别对应onkeydown. onkeypress和onkeyup这 ...

  10. IOI2016Day2&period; paint

    题目链接:http://uoj.ac/problem/238 题目大意: 有一个长度为n的黑白序列,告诉你所以k个极长连续黑段长度和顺序.有一些位置的颜色已知,需要判断剩下未知的位置哪些颜色 一定是白 ...