P7324-[WC2021]表达式求值【dp】
2024-09-04 21:33:32
正题
题目链接:https://www.luogu.com.cn/problem/P7324
题目大意
给一个只包含\(m\)个值的表达式,\(<\)表前后取最小值,\(>\)表前后取最大,\(?\)可以是小于也可以是大于。
然后\(n\)次给出这\(m\)个值,所有方案下表达式取值的和。输出这\(n\)次答案的和。
\(1\leq n\leq 5\times 10^4,1\leq m\leq 10,1\leq |S|\leq 5\times 10^4\)
解题思路
有括号所以先把表达树建出来,考虑到\(m\)很小,应该和状压有点关系。暴力的做法是直接做\(n\)次,时间复杂度是\(O(nm|S|)\)显然过不了。
因为取值只有\(m\)个,考虑把所有的信息压缩起来。实际上我们需要的信息就只有\(m\)个数之间的大小顺序,这样的状态数是\(m!\)个,要搞起来时间复杂度最快是\(O(m!|S|)\)也过不了。
但是对于一个数字来说我们就只需啊哟考虑它和其他数字的大小关系,状态数是\(2^m\)。设\(f_{x,s,0/1}\)表示到节点\(x\)时,小于数字\(x\)的值状态是\(s\)时到该节点的数字小于/大于数字\(x\)的方案数。
然后对于每个\(s\)跑出来一个答案,然后按照这个后面就很好做了。
时间复杂度\(O(2^m|S|+nm\log n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define ll long long
using namespace std;
const ll N=1e5+10,P=1e9+7;
ll n,m,k,cnt,L,ans,a[10][N],p[10],rev[N];
ll ls[N],rs[N],f[N][2],z[N],c[N];
char s[N];stack<ll> st;
ll Build(ll l,ll r){
if(l==r){++cnt;c[cnt]=s[l]-'0';return cnt;}
if(rev[r]==l)return Build(l+1,r-1);
ll x=++cnt;
if(rev[r]){
ls[x]=Build(l,rev[r]-2);
rs[x]=Build(rev[r]+1,r-1);
c[x]=s[rev[r]-1];
}
else{
ls[x]=Build(l,r-2);
rs[x]=Build(r,r);
c[x]=s[r-1];
}
return x;
}
void dfs(ll x,ll s){
f[x][0]=f[x][1]=0;
if(c[x]<10){
f[x][!(s&(1<<c[x]))]=1;
return;
}
dfs(ls[x],s);dfs(rs[x],s);
if(c[x]!='>'){
for(ll i=0;i<2;i++)
for(ll j=0;j<2;j++)
(f[x][min(i,j)]+=f[ls[x]][i]*f[rs[x]][j]%P)%=P;
}
if(c[x]!='<'){
for(ll i=0;i<2;i++)
for(ll j=0;j<2;j++)
(f[x][max(i,j)]+=f[ls[x]][i]*f[rs[x]][j]%P)%=P;
}
return;
}
bool cmp(ll x,ll y)
{return a[x][k]<a[y][k];}
signed main()
{
scanf("%lld%lld",&n,&m);
for(ll i=0;i<m;i++)
for(ll j=1;j<=n;j++)
scanf("%lld",&a[i][j]);
scanf("%s",s+1);L=strlen(s+1);
for(ll i=1;i<=L;i++){
if(s[i]=='(')st.push(i);
else if(s[i]==')'){
ll x=st.top();
rev[x]=i;rev[i]=x;
st.pop();
}
}
Build(1,L);
ll MS=(1<<m);
for(ll i=0;i<MS;i++)
dfs(1,i),z[i]=f[1][1];
for(k=1;k<=n;k++){
for(ll i=0;i<m;i++)p[i]=i;
sort(p,p+m,cmp);
(ans+=z[0]*a[p[0]][k]%P)%=P;
ll S=0;
for(ll i=1;i<m;i++){
S|=(1<<p[i-1]);
(ans+=z[S]*(a[p[i]][k]-a[p[i-1]][k])%P)%=P;
}
}
printf("%lld\n",(ans+P)%P);
return 0;
}
最新文章
- Java获取XML节点总结之读取XML文档节点
- 安装使用ubuntu问题汇总
- ASP.NET 5系列教程 (三):view components介绍
- (转) Python Generators(生成器)——yield关键字
- setTimeout/setInterval执行时机
- 【原创】一起学C++ 之->;(箭头符号) ---------C++ primer plus(第6版)
- 如何使用ASP.NET Web API OData在Oracle中使用Entity Framework 6.x Code-First方式开发 OData V4 Service
- Install TightVNC Server in RHEL/CentOS and Fedora to Access Remote Desktops
- 《Python学习手册》读书笔记
- hadoop集群环境的搭建
- mysql 主主+ Keepalived 高可用
- Windows 10 无法使用搜索栏,显示一片空白
- 转载 -- CSS3 中关于 select 下拉列表的样式
- Intellij-插件安装-JRebel热部署插件安装
- textarea 固定大小,滚动条,限制拖动,文字对齐
- oracle 实例名,数据库名概念
- Hadoop日记Day4---去除HADOOP_HOME is deprecated
- [转][Dapper]SQL 经验集
- LocalStorage、SessionStorage使用详解
- SpringBoot application.properties 配置项详解