Arithmetic of Bomb
众所周知，度度熊非常喜欢数字。
它最近在学习小学算术，第一次发现这个世界上居然存在两位数，三位数……甚至N位数！
但是这回的算术题可并不简单，由于含有表示bomb的#号，度度熊称之为 Arithmetic of Bomb。
Bomb Number中的bomb，也就是#号，会展开一些数字，这会导致最终展开的数字超出了度度熊所能理解的范畴。比如”(1)#(3)”表示”1”出现了3次，将会被展开为”111”，
同理，”(12)#(2)4(2)#(3)”将会被展开为”12124222”。
为了方便理解，下面给出了Bomb Number的BNF表示。
<bomb number> := <bomb term> | <bomb number> <bomb term> <bomb term> := <number> | '(' <number> ')' '#' '(' <non-zero-digit> ')' <number> := <digit> | <digit> <number> <digit> := '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' <non-zero-digit> := '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
请将Bomb Number中所有的#号展开，由于数字可能很长，结果对 1 000 000 007 取模。
1
111
12124222
212121205
#include <bits/stdc++.h>
using namespace std;
const int MD=1e9+7;
int c[10005];
char s[10005];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%s",s+1);
int ans=0;
for(int i=1;s[i];)
{
if(s[i]=='(')
{
int j=i+1,n2=0,n=0;
while(s[j]!=')')
{
c[++n]=s[j]-48;
j++;
}
j+=3;
while(s[j]!=')')
{
n2=n2*10+s[j]-48;
j++;
}
for(int j=n+1;j<=n*n2;j++)
c[j]=c[(j-1)%n+1];
for(int j=1;j<=n*n2;j++)
ans=(1ll*ans*10+c[j])%MD;
i=j+1;
}
else
{
int j=i;
int n=0;
while(s[j]!='('&&s[j])
{
c[++n]=s[j]-48;
j++;
}
for(int j=1;j<=n;j++)
ans=(1ll*ans*10+c[j])%MD;
i=j;
}
}
printf("%d\n",ans);
}
return 0;
}
Pokémon GO
众所周知，度度熊最近沉迷于 Pokémon GO。
今天它决定要抓住所有的精灵球！
为了不让度度熊失望，精灵球已经被事先放置在一个2*N的格子上，每一个格子上都有一个精灵球。度度熊可以选择任意一个格子开始游戏，抓捕格子上的精灵球，然后移动到一个相邻的至少有一个公共点的格子上继续抓捕。例如，(2, 2) 的相邻格子有(1, 1), (2, 1) 和 (1, 2) 等等。
现在度度熊希望知道将所有精灵球都抓到并且步数最少的方案数目。两个方案被认为是不同，当且仅当两个方案至少有一步所在的格子是不同的。
2
24
96
#include <bits/stdc++.h>
using namespace std;
typedef __int64 LL;
const int N=1e4+5;
const LL MD=1e9+7;
LL f[N],dp[N];
int main()
{
f[0]=1;
f[1]=2;
for(int i=2; i<N; i++)
f[i]=(f[i-1]<<1)%MD;
dp[0]=0;
dp[1]=0;
for(int i=2; i<N; i++)
dp[i]=(4*(f[i-2]+dp[i-2])+2*(f[i-1]+dp[i-1]))%MD;
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
LL ans=0;
for(int i=1;i<=n;i++)
{
if(i==1||i==n)
{
ans=(ans+f[n]+dp[n])%MD;
}
else
{
ans=(ans+f[i]*(f[n-i]+dp[n-i])%MD)%MD;
ans=(ans+f[n-i+1]*(f[i-1]+dp[i-1])%MD)%MD;
}
}
cout<<ans<<endl;
}
return 0;
}
Valley Numer
众所周知，度度熊非常喜欢数字。
它最近发明了一种新的数字：Valley Number，像山谷一样的数字。
当一个数字，从左到右依次看过去数字没有出现先递增接着递减的“山峰”现象，就被称作 Valley Number。它可以递增，也可以递减，还可以先递减再递增。在递增或递减的过程中可以出现相等的情况。
比如，1，10，12，212，32122都是 Valley Number。
121，12331，21212则不是。
度度熊想知道不大于N的Valley Number数有多少。
注意，前导0是不合法的。
3
14
119
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
string s;
ll dp[105][10][3][2][2];
int dfs(int p, int now, int sta, int f, int st) {
if (p == s.size()) return 1;
if (dp[p][now][sta][f][st] != -1) return dp[p][now][sta][f][st];
ll& ret = dp[p][now][sta][f][st];
ret = 0;
for (int i = 0; i <= (f ? s[p] - '0' : 9); i++) {
if (sta == 1) {
ret = (ret + dfs(p + 1, (i == 0 && st ? 9 : i), (i <= now ? 1 : 2), f && i == s[p] - '0', st && i == 0)) % mod;
}
if (sta == 2 && i >= now) {
ret = (ret + dfs(p + 1, (i == 0 && st ? 9 : i), 2, f && i == s[p] - '0', st && i == 0)) % mod;
}
}
return ret;
}
int main(int argc, char *argv[]) {
int T;
cin >> T;
while (T--) {
memset(dp, -1, sizeof(dp));
cin >> s;
cout << (dfs(0, 9, 1, 1, 1) + mod - 1) % mod << endl;
}
return 0;
}
alley Numer II
众所周知，度度熊非常喜欢图。
它最近发现了图中也是可以出现 valley —— 山谷的，像下面这张图。
为了形成山谷，首先要将一个图的顶点标记为高点或者低点。标记完成后如果一个顶点三元组<X, Y, Z>中，X和Y之间有边，Y与Z之间也有边，同时X和Z是高点，Y是低点，那么它们就构成一个valley。
度度熊想知道一个无向图中最多可以构成多少个valley，一个顶点最多只能出现在一个valley中。