-
给定一个程序,包含下列语句:
begin
:开始程序。loop x
:开始一个(x)次的循环,其中(x)为正整数或(n)。op x
:执行(x)个单位的操作,其中(x)为正整数或(n)。break
:直接退出循环。continue
:跳过这次循环的剩余语句,直接进入下一次循环。end
:结束程序/循环。
-
求一个多项式(不能忽略常数项和系数),表示最终复杂度。
-
循环层数(le20),最终系数(le10^9)
此题数据出锅
尽管题目中保证了(x)为正整数或(n),然而数据中依然出现了(x=0)的情况。。。
为了通过此题,必须特判一下,如果loop x
操作中(x=0),将其视作(x=n)。
纯粹模拟
显然这种东西是要对每层循环开栈进行模拟的,对此考虑开一堆奇奇怪怪的数组:
- (S[x],P[x]):分别表示进入第(x)层循环所有系数之积以及(n)的次数。
- (G[x]):表示第(x)层循环的循环次数
x
(可以用(G[x]=0)表示(n))。 - (C[x][y]):记录第(x)层循环(y)次项的系数。
然后对于每种操作分类讨论:
loop
:进入一个新的循环,求出(G[T]),然后据此在(S[T-1])和(P[T-1])的基础上进行修正。op
:如果(x=n),给(C[T][P[T]+1])加上(S[T]);否则给(C[T][P[T]])加上(S[T] imes x)。break
:相当于这个循环只执行了一次,所以消去(G[T])的贡献,然后忽视这个循环之后的语句(忽视可以用(S[T]=0)标记)。continue
:只要忽视这个循环之后的语句就好了。end
:把这个循环的贡献加到前一个循环中。
口胡起来就是这样,具体实现还是有一些细节的,详见代码。。。
代码:(O(20|s|))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 30
#define LL long long
using namespace std;
int n,P[N+5];LL ans[N+5],G[N+5],S[N+5],C[N+5][N+5];string s;
int main()
{
RI T=0,i;LL x;ios::sync_with_stdio(false),cin>>s,S[0]=1,P[0]=0;W(~T)
{
if(cin>>s,s=="loop")//循环
{
if(++T,S[T]=S[T-1],P[T]=P[T-1],cin>>s,s=="0"||s=="n") {G[T]=0,++P[T];continue;}//如果x=n(因数据出锅有x=0)
for(x=i=0;i^s.length();++i) x=x*10+(s[i]&15);G[T]=x,S[T]*=x;continue;//如果x为正整数
}
if(s=="op")//操作
{
if(cin>>s,!S[T]) continue;if(s=="n") {C[T][P[T]+1]+=S[T];continue;}//如果x=n
for(x=i=0;i^s.length();++i) x=x*10+(s[i]&15);C[T][P[T]]+=S[T]*x;continue;//如果x为正整数
}
if(s=="break")//退出循环
{
if(!T||!S[T]) continue;if(!G[T]) for(i=0;i<=N;++i) C[T][i]=C[T][i+1];//如果G[T]=n
else for(i=0;i<=N;++i) C[T][i]/=G[T];S[T]=0;continue;//如果G[T]为正整数
}
if(s=="continue") {T&&(S[T]=0);continue;}//跳过循环,直接忽视后面语句
if(s=="end") {for(i=0;i<=N;++i) (T?C[T-1]:ans)[i]+=C[T][i],C[T][i]=0;--T;continue;}//结束循环,把贡献归到上一层循环
}
for(x=0,i=N;~i;--i) ans[i]&&(x?(cout<<'+',0):(x=1),//输出答案
(!i||ans[i]^1)&&(cout<<ans[i],0),i&&(cout<<'n',i^1&&(cout<<'^'<<i,0)));//注意一些判断
return !x&&(cout<<'0'<<endl),0;
}