考虑暴力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(动态规划+拉格朗日插值法)的更多相关文章
-
BZOJ2655 Calc - dp 拉格朗日插值法
BZOJ2655 Calc 参考 题意: 给定n,m,mod,问在对mod取模的背景下,从[1,m]中选出n个数相乘可以得到的总和为多少. 思路: 首先可以发现dp方程 ,假定dp[m][n]表示从[ ...
-
【BZOJ】2655: calc 动态规划+拉格朗日插值
[题意]一个序列$a_1,...,a_n$合法当且仅当它们都是[1,A]中的数字且互不相同,一个序列的价值定义为数字的乘积,求所有序列的价值和.n<=500,A<=10^9,n+1< ...
-
BZOJ2655: calc(dp 拉格朗日插值)
题意 题目链接 Sol 首先不难想到一个dp 设\(f[i][j]\)表示选了\(i\)个严格递增的数最大的数为\(j\)的方案数 转移的时候判断一下最后一个位置是否是\(j\) \[f[i][j] ...
-
[BZOJ2655]calc(拉格朗日插值法+DP)
2655: calc Time Limit: 30 Sec Memory Limit: 512 MBSubmit: 428 Solved: 246[Submit][Status][Discuss] ...
-
[国家集训队] calc(动规+拉格朗日插值法)
题目 P4463 [国家集训队] calc 集训队的题目真是做不动呀\(\%>\_<\%\) 朴素方程 设\(f_{i,j}\)为前\(i\)个数值域\([1,j]\),且序列递增的总贡献 ...
-
bzoj千题计划269:bzoj2655: calc (拉格朗日插值)
http://www.lydsy.com/JudgeOnline/problem.php?id=2655 f[i][j] 表示[1,i]里选严格递增的j个数,序列值之和 那么ans=f[A][n] * ...
-
Matlab数值计算示例: 牛顿插值法、LU分解法、拉格朗日插值法、牛顿插值法
本文源于一次课题作业,部分自己写的,部分借用了网上的demo 牛顿迭代法(1) x=1:0.01:2; y=x.^3-x.^2+sin(x)-1; plot(x,y,'linewidth',2);gr ...
-
拉格朗日插值法——用Python进行数值计算
插值法的伟大作用我就不说了.... 那么贴代码? 首先说一下下面几点: 1. 已有的数据样本被称之为 "插值节点" 2. 对于特定插值节点,它所对应的插值函数是必定存在且唯一的(关 ...
-
CPP&;MATLAB实现拉格朗日插值法
开始学习MATLAB(R和Python先放一放...),老师推荐一本书,看完基础就是各种算法...首先是各种插值.先说拉格朗日插值法,这原理楼主完全不懂的,查的*,好久才看懂.那里讲的很详细,这 ...
随机推荐
-
c#中两种不同的存储过程调用与比较
存储过程简介 简单的说,存储过程是由一些SQL语句和控制语句组成的被封装起来的过程,它驻留在数据库中,可以被客户应用程序调用,也可以从另一个过程或触发器调用.它的参数可以被传递和返回.与应用程序中的函 ...
-
【转载】Pyqt QSplitter分割窗口
转载来自: http://blog.sina.com.cn/s/blog_4b5039210100h3ih.html 分割窗口在应用程序中经常用到,它可以灵活分布窗口布局,经常用于类似文件资源管理器的 ...
-
Binary Tree 分类: POJ 2015-06-12 20:34 17人阅读 评论(0) 收藏
Binary Tree Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 6355 Accepted: 2922 Descr ...
-
JS计算字符串所占字节数
最近项目有个需求要用js计算一串字符串写入到localStorage里所占的内存,众所周知的,js是使用Unicode编码的.而Unicode的实现有N种,其中用的最多的就是UTF-8和UTF-16. ...
-
接收Firfox RESTClient #Post请求
什么是 RESTClient 请参考:http://www.blogjava.net/paulwong/archive/2014/04/19/412688.html 对接接口时经常会需要传个异步回调消 ...
-
DIV+CSS外部字体引用
注意: 由于各个浏览器兼容问题大家还是少用这个,下面是具体的使用方法和效果截图: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN&qu ...
-
liunx下NetworkManager导致网卡不能启动
前几天在客户现场,配置一台系统为redhat 6.0的服务器,这台服务器是IBM x3755,系统是预装的.在把服务器的IP地址配置完成后,使用命令不能启动网卡.提示:弹出界面 eht0:错误:激活链 ...
-
.Net程序员学用Oracle系列(26):PLSQL 之类型、变量和结构
1.类型 1.1.属性类型 1.2.记录类型 2.变量 2.1.变量类型 2.2.变量定义 2.3.变量赋值 3.结构 3.1.顺序结构 3.2.选择结构 3.3.循环结构 4.总结 1.类型 在&l ...
-
JS键盘事件对象之keyCode、charCode、which属性对比
先说一些有关键盘事件的事项:用js实现键盘记录,要关注浏览器的三种按键事件类型,即keydown,keypress和keyup,它们分别对应onkeydown. onkeypress和onkeyup这 ...
-
IOI2016Day2. paint
题目链接:http://uoj.ac/problem/238 题目大意: 有一个长度为n的黑白序列,告诉你所以k个极长连续黑段长度和顺序.有一些位置的颜色已知,需要判断剩下未知的位置哪些颜色 一定是白 ...