博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【BZOJ】4559: [JLoi2016]成绩比较 计数DP+排列组合+拉格朗日插值
阅读量:6703 次
发布时间:2019-06-25

本文共 2412 字,大约阅读时间需要 8 分钟。

【题意】n位同学(其中一位是B神),m门必修课,每门必修课的分数是[1,Ui]。B神碾压了k位同学(所有课分数<=B神),且第x门课有rx-1位同学的分数高于B神,求满足条件的分数情况数。当有一位同学的一门必修课分数不同时视为两种情况不同。n,m<=100,Ui<=10^9。

【算法】计数DP+排列组合+拉格朗日插值

【题解】把分数作为状态不现实,只能逐门课考虑。

设$f[i][j]$表示前i门课,有j个同学被碾压的情况数,则有:

$$f[i][j]=g(i)\cdot\sum_{k=j}^{n}f[i-1][k]\cdot\binom{k}{k-j}\cdot\binom{n-k-1}{r_i-1-k+j}$$

解释:首先可以发现当天分数需要高于B神的人数是确定的,和多少人被碾压等信息无关,所以令g(i)表示第i门课的合法分数情况数,独立计算。

枚举前i-1门课被碾压的人数k,那么ri-1由两部分组成,一部分是不再被碾压的k-j人(从k人中选出),剩余的ri-1-k+j人从原本就未被碾压的n-k-1人中选出。

考虑计算g(i),枚举B神的分数i,则有r-1人的选择范围是[i+1,Ui],另外n-r人的选择范围是[1,i],即:

$$g(i)=\sum_{i=1}^{U_i}(U_i-i)^{r_i-1}*i^{n-r}$$

Ui太大了,考虑将Ui当成自变量后用拉格朗日插值解决,即:

$$f(x)=\sum_{i=1}^{x}(x-i)^{r-1}*i^{n-r}$$

现在我们要求f(Ui)的值,需要确定多项式的次数。网上的解释都看不懂,强行理解:令i=x/2,那么式子右边的i也可以表示为(n-i),合并后次数为n-1,再加上Σ的上届为x,那么最高次就是n,这是一个n次多项式。

于是我们可以对每个i,O(n^2)枚举前n+1个点的值来插值得到f(Ui)。DP转移的复杂度也是O(n)的。

总复杂度O(n^3)。

#include
#include
using namespace std;const int maxn=110,MOD=1e9+7;int v[maxn],n,m,kind,u[maxn],r[maxn],g[maxn],f[maxn][maxn],c[maxn][maxn];int power(int x,int k){
int ans=1;while(k){
if(k&1)ans=1ll*ans*x%MOD;x=1ll*x*x%MOD;k>>=1;}return ans;}int inv(int x){
return power(x,MOD-2);}int M(int x){
return x>=MOD?x-MOD:x;}int solve(int u,int r){ for(int x=1;x<=n+1;x++){ g[x]=0;//! for(int i=1;i<=x;i++){ g[x]=M(g[x]+1ll*power(x-i,r-1)*power(i,n-r)%MOD); } if(x==u)return g[x]; } for(int i=1;i<=n+1;i++){ v[i]=1; for(int j=1;j<=n+1;j++)if(i!=j)v[i]=1ll*v[i]*(i-j+MOD)%MOD; v[i]=inv(v[i]); } int ans=0; for(int i=1;i<=n+1;i++){ int w=1ll*g[i]*v[i]%MOD; for(int j=1;j<=n+1;j++)if(i!=j)w=1ll*w*(u-j+MOD)%MOD;//i!=j ans=M(ans+w); } return ans;}int main(){ scanf("%d%d%d",&n,&m,&kind); for(int i=0;i<=n;i++){ c[i][0]=1; for(int j=1;j<=i;j++){ c[i][j]=M(c[i-1][j-1]+c[i-1][j]); } } for(int i=1;i<=m;i++)scanf("%d",&u[i]); for(int i=1;i<=m;i++)scanf("%d",&r[i]); f[0][n-1]=1; for(int i=1;i<=m;i++){ int g=solve(u[i],r[i]); for(int j=kind;j<=n;j++){ for(int k=j;k<=n;k++)if(r[i]-1-k+j>=0&&r[i]-1-k+j<=n-k-1){ f[i][j]=M(f[i][j]+1ll*f[i-1][k]*c[k][k-j]%MOD*c[n-k-1][r[i]-1-k+j]%MOD); } f[i][j]=1ll*f[i][j]*g%MOD; } } printf("%d",f[m][kind]); return 0;}
View Code

 

转载于:https://www.cnblogs.com/onioncyc/p/8831107.html

你可能感兴趣的文章
华泰证券:如何自研高效可靠的交易系统通信框架?
查看>>
蚂蚁数据分析平台的演进及数据分析方法的应用
查看>>
Mozilla正在SpiderMonkey中测试JavaScript并行计算
查看>>
Node.js 6.0支持93%的ES2015语法
查看>>
Elixir 1.2带来多项功能增强和性能提升
查看>>
慎用!BLEU评价NLP文本输出质量存在严重问题
查看>>
避免标准数据模型
查看>>
【js】async和await使用
查看>>
如何定义性能需求
查看>>
管理之善,在于让员工有机会试错
查看>>
ASP.NET Core 2加入了Razor页面特性
查看>>
Idris趋近发布1.0版
查看>>
微服务之旅的经验分享
查看>>
访谈:关于持续敏捷交付与服务矩阵
查看>>
Dependabot:自动创建GitHub PR修复潜在漏洞
查看>>
ticketea如何从一体化转向多体化架构
查看>>
树莓派第三代跨越发展,采用64位处理器内建WiFi及蓝牙
查看>>
如何选取Linux容器镜像
查看>>
姜宁谈红帽绩效考核:不关心员工具体做什么
查看>>
微软推出VS Code新特性,为TypeScript和JavaScript用户提供AI辅助开发功能
查看>>