YZOJ P3629 [校内训练20180406]表达式

时间限制：1000MS 内存限制：131072KB

出题人：zzx 难度： $6.5$

题目描述

本题中，我们需要计算一些“Bomb表达式”的结果。比如， “1-2+3” 的结果为 2 。和普通表达式不同的是，Bomb表达式中可能包含一些 “#” 号，会展开一些普通表达式。比如 “(1-2+3)#(3)” 表示 “1-2+3 ”出现了 3 次，将会被展开为 “1-2+31-2+31-2+3”，其结果为 60 。

为了方便理解，下面给出了Bomb表达式（bomb expression）和普通表达式（normal expression）的BNF表示。

<bomb expression> := <bomb term> | <bomb expression> <bomb term>
<bomb term> := <bomb statement> | '(' <bomb statement> ')' '#' '(' <number> ')'
<bomb statement> := <bomb element> | <bomb statement> <bomb element>
<bomb element> := <digit> | '+' | '-' | '*'
<normal expression> := <norm term> | <normal expression> '+' <norm term> | <normal expression> '-' <norm term>
<norm term> := <number> | <norm term> '*' <number>
<number> := <digit> | <non-zero-digit> <number>
<digit> := '0' | <non-zero-digit>
<non-zero-digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

<bomb term> := <bomb statement> | '(' <bomb statement> ')' '#' '(' <number> ')'

<bomb element> := <digit> | '+' | '-' | '*'

<non-zero-digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

请先将Bomb表达式中所有的 # 号展开，使其成为普通表达式（题目的输入保证展开后是一个合法的普通表达式），然后计算这个表达式的结果。

输入格式

第一行一个正整数 $T$ ，表示输入数据组数。

接下来 $T$ 行，每行一个字符串，为待计算的Bomb表达式。

输出格式

对于每组数据输出一行一个整数，表示表达式的结果，答案对 $1,000,000,007$ 取模。

样例输入

7
1-2+3
(1-2+3)#(3)
(1+2-3)#(3)
(1)#(3)
(1+)#(2)1
(2*3+1)#(2)
(2)#(2)1+1(2)#(2)

1-2+3

(1-2+3)#(3)

(1+2-3)#(3)

(1)#(3)

(1+)#(2)1

(2*3+1)#(2)

(2)#(2)1+1(2)#(2)

样例输出

999999949

111

343

数据规模与约定

对于 $100\%$ 的数据， $1 \leq T \leq 50$ ，输入表达式的总长度不超过 $300,000$ ，<bomb term> 中的 <number> 不超过 $10^{18}$ 。

神仙题目

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cstdarg>

#define MOD 1000000007

struct _vec
{
	int a[4];
	_vec(int ta=0,int tb=0,int tc=0,int td=0){a[0]=ta,a[1]=tb,a[2]=tc,a[3]=td;}
};

struct _mat
{
	int a[4][4];
	_mat(){memset(a,0,sizeof(a));}
	inline void fill(int cnt,...)
	{
		va_list ap;
		va_start(ap,cnt);
		for(register int i=0;i<4 && cnt;i++)
			for(register int j=0;j<4 && cnt;j++,cnt--)
				a[i][j]=va_arg(ap,int);
		va_end(ap);
	}
	_mat operator * (const _mat&o)const
	{
		_mat ans;
		for(register int i=0;i<4;i++)
			for(register int j=0;j<4;j++)
				for(register int k=0;k<4;k++)
					(ans.a[i][j]+=(long long)this->a[i][k]*o.a[k][j]%MOD)%=MOD;
		return ans;
	}
	_vec operator * (const _vec&o)const
	{
		_vec ans;
		for(register int i=0;i<4;i++)
			for(register int j=0;j<4;j++)
				(ans.a[i]+=(long long)this->a[i][j]*o.a[j]%MOD)%=MOD;
		return ans;
	}
}I,MD,MA,MM,MT,ML;

inline _mat GetNumMat(register int x)
{
	_mat c=MD;
	c.a[2][1]=x;
	return c;
}

template<class T>
inline bool MatchAns(T&ans,register char c)
{
	if(c=='+')
		ans=MA*ans;
	else if(c=='-')
		ans=MM*ans;
	else if(c=='*')
		ans=MT*ans;
	else if(c>='0' && c<='9')
		ans=GetNumMat(c-'0')*ans;
	else
		return false;
	return true;
}

inline _mat _pow(_mat base,long long b)
{
	_mat ans=I;
	while(b)
	{
		if(b&1)
			ans=ans*base;
		base=base*base;
		b>>=1;
	}
	return ans;
}

char s[305050];

int main()
{
	I.fill(16, 1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1);
	MD.fill(16, 1,0,0,0, 0,1,0,0, 0,0xFF,10,0, 0,0,0,1);
	MA.fill(16, 1,0,1,0, 0,0,0,1, 0,0,0,0, 0,0,0,1);
	MM.fill(16, 1,0,1,0, 0,0,0,-1, 0,0,0,0, 0,0,0,1);
	MT.fill(16, 1,0,0,0, 0,0,1,0, 0,0,0,0, 0,0,0,1);
	
	int T;scanf("%d",&T);
	for(register int lp=1;lp<=T;lp++)
	{
		_vec ans(0,1,0,1);
		scanf("%s",&s[1]);
		register int ls=strlen(&s[1]);
		for(register int i=1;i<=ls;i++)
			if(!MatchAns(ans,s[i]))
			{
				i++;
				_mat now=I;
				for(;i<=ls;i++)
					if(!MatchAns(now,s[i]))
						break;
				long long cnt=0;
				for(i+=3;s[i]!=')' && i<=ls;i++)
					cnt=cnt*10+s[i]-'0';
				ans=_pow(now,cnt)*ans;
			}
		ans=MA*ans;
		printf("%d\n",(ans.a[0]+MOD)%MOD);
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <climits>

#include <cstdarg>

#define MOD 1000000007

struct _vec

{

int a[4];

_vec(int ta=0,int tb=0,int tc=0,int td=0){a[0]=ta,a[1]=tb,a[2]=tc,a[3]=td;}

};

struct _mat

{

int a[4][4];

_mat(){memset(a,0,sizeof(a));}

inline void fill(int cnt,...)

{

va_list ap;

va_start(ap,cnt);

for(register int i=0;i<4 && cnt;i++)

for(register int j=0;j<4 && cnt;j++,cnt--)

a[i][j]=va_arg(ap,int);

va_end(ap);

}

_mat operator * (const _mat&o)const

{

_mat ans;

for(register int i=0;i<4;i++)

for(register int j=0;j<4;j++)

for(register int k=0;k<4;k++)

(ans.a[i][j]+=(long long)this->a[i][k]*o.a[k][j]%MOD)%=MOD;

return ans;

}

_vec operator * (const _vec&o)const

{

_vec ans;

for(register int i=0;i<4;i++)

for(register int j=0;j<4;j++)

(ans.a[i]+=(long long)this->a[i][j]*o.a[j]%MOD)%=MOD;

return ans;

}

}I,MD,MA,MM,MT,ML;

inline _mat GetNumMat(register int x)

{

_mat c=MD;

c.a[2][1]=x;

return c;

}

template<class T>

inline bool MatchAns(T&ans,register char c)

{

if(c=='+')

ans=MA*ans;

else if(c=='-')

ans=MM*ans;

else if(c=='*')

ans=MT*ans;

else if(c>='0' && c<='9')

ans=GetNumMat(c-'0')*ans;

else

return false;

return true;

}

inline _mat _pow(_mat base,long long b)

{

_mat ans=I;

while(b)

{

if(b&1)

ans=ans*base;

base=base*base;

b>>=1;

}

return ans;

}

char s[305050];

int main()

{

I.fill(16, 1,0,0,0, 0,1,0,0, 0,0,1,0, 0,0,0,1);

MD.fill(16, 1,0,0,0, 0,1,0,0, 0,0xFF,10,0, 0,0,0,1);

MA.fill(16, 1,0,1,0, 0,0,0,1, 0,0,0,0, 0,0,0,1);

MM.fill(16, 1,0,1,0, 0,0,0,-1, 0,0,0,0, 0,0,0,1);

MT.fill(16, 1,0,0,0, 0,0,1,0, 0,0,0,0, 0,0,0,1);

int T;scanf("%d",&T);

for(register int lp=1;lp<=T;lp++)

{

_vec ans(0,1,0,1);

scanf("%s",&s[1]);

for(register int i=1;i<=ls;i++)

if(!MatchAns(ans,s[i]))

{

i++;

_mat now=I;

for(;i<=ls;i++)

if(!MatchAns(now,s[i]))

break;

long long cnt=0;

for(i+=3;s[i]!=')' && i<=ls;i++)

cnt=cnt*10+s[i]-'0';

ans=_pow(now,cnt)*ans;

}

ans=MA*ans;

printf("%d\n",(ans.a[0]+MOD)%MOD);

}

return 0;

}

YZOJ P3629 [校内训练20180406]表达式

题目描述

输入格式

输出格式

样例输入

样例输出

数据规模与约定

发表回复 取消回复

发表回复取消回复