P7088 题解

· · 题解

首先考虑如何存储向量。关注到向量与向量之间的操作是每一维分开的，所以我们存储一个多项式表示每一维上经过操作后与 X 的对应维上的对应关系。三种双目运算和取负、平方都对应多项式上的运算，只有折叠操作特殊。

对于折叠操作，我们预处理每一个幂次 j 的 \sum\limits_{i=1}^NX_i^j，然后折叠操作也是可以在多项式次数内完成的。

用多项式存储看起来很错，因为正常情况下会被卡到 2^N 次（全是平方操作）。但是关注到题目中给定了复杂度这一定义，与多项式的次数完全相等。因为复杂度不超过 10，所以用多项式存只用存 10 次的系数，暴力乘法即可。

时间复杂度 O(np^2)，其中 p 是运算式的复杂度。

代码细节较多，主要在于：

  1. 取负这一操作要与减法操作区分开来。
  2. 对于单目运算符计算之前要把取负都先算掉。

Code：

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"(function %s, line #%d): " fmt,__func__,__LINE__,##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=1e5+5,mod=1e9;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
// -----------------template-------------------
int n;ll a[N],p[N],sum[11];
char s[N];int m;

struct Poly{
  ll a[11];
  Poly(){For(i,0,10) a[i]=0;}
  Poly(int x){For(i,1,10) a[i]=0;a[0]=x;}
  ll& operator[](int x){return a[x];}
  ll sum(){ll res=0;For(i,0,10) res=(res+a[i]*::sum[i])%mod;return res;} // 计算折叠的答案
};
int add(int x,int y){x+=y;if(x>=mod) return x-mod;else return x;}
int suc(int x,int y){x-=y;if(x<0) return x+mod;else return x;}
Poly operator+(Poly a,Poly b){For(i,0,10) a[i]=add(a[i],b[i]);return a;}
Poly operator-(Poly a,Poly b){For(i,0,10) a[i]=suc(a[i],b[i]);return a;}
Poly operator*(Poly a,Poly b){Poly c;For(i,0,10) For(j,0,10-i) c[i+j]=(c[i+j]+a[i]*b[j])%mod;return c;}
//---------------少项式-------------------
stack<Poly>val;
stack<char>op;
void flatMinus(){ // 每次运算前把取负给做掉
  while(!op.empty()&&op.top()=='-'){
    auto p=val.top();val.pop();
    val.emplace(Poly()-p);op.pop();
  }
}
void getCalc(){ // 计算 val 的前两项和 op 中的第一项运算后的结果
  char t=op.top();op.pop();
  Poly x=val.top();val.pop();
  Poly y=val.top();val.pop();
  if(t=='+') x=x+y;
  else if(t=='-') x=x-y;
  else if(t=='*') x=x*y;
  else assert(0);
  val.emplace(x);
}
void emplace_op(char x){flatMinus();op.emplace(x);}
void emplace_val(Poly x){
  val.emplace(x);
  if(!op.empty()&&op.top()!=')') getCalc();
}
signed LJY(){
  n=read();For(i,1,n) a[i]=read();
  For(i,1,n) p[i]=1;sum[0]=n;
  For(i,1,10){
    For(j,1,n) p[j]=p[j]*a[j]%mod;
    For(j,1,n) sum[i]=add(sum[i],p[j]); // 预处理幂次和
  }scanf("%s",s+1);m=strlen(s+1);
  Poly X;X[1]=1;op.emplace(')');
  ForDown(i,m,1){
    if(s[i]=='X') emplace_val(X);
    else if(s[i]=='N') emplace_val(n);
    else if(isdigit(s[i])){
      ll sp=0,pw=1;int j=i;
      while(j&&isdigit(s[j])){
        sp=sp+pw*(s[j]-'0');
        j--;pw=pw*10%mod;
      }emplace_val(sp);i=j+1;
    }
    else if(s[i]=='/'){
      flatMinus();Poly x=val.top();val.pop();
      emplace_val(x.sum());i--;
    }else if(s[i]==':'){
      flatMinus();
      Poly x=val.top();val.pop();
      emplace_val(x*x);i--;
    }else if(s[i]==')') op.emplace(')');
    else if(s[i]=='('){ // 去掉一层括号
      flatMinus(),op.pop();
      if(!op.empty()&&op.top()!=')') getCalc();
    }
    else emplace_op(s[i]);
  }flatMinus();printf("%d\n",val.top()[0]);
  return 0;
}