# 某岛

… : "…アッカリ～ン . .. . " .. .
August 19, 2015

# 2015 Multi-University Training Contest 9 － Host by xudyh

## 1001

```#include <iostream>
#include <cstring>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define RST(A) memset(A, 0, sizeof(A))

typedef long long LL;
const int MOD = int(1e9) + 7;

struct Int{
int val;

operator int() const{return val;}

Int(int t){
val = t;
}
Int& operator -=(const int& rhs){
val -= rhs; if (val < 0) val += MOD;
return *this;
}
Int& operator +=(const int& rhs){
val += rhs; if (val >= MOD) val -= MOD;
return *this;
}
Int operator *(const int& rhs) const{
LL z = (LL) val * rhs % MOD;
return z;
}
};

const int N = int(1e2) + 9;

int a[N]; char op[N];
int Fact[N], Binom[N][N], dp[N][N];
int n;

int w(int l, int r){
return Fact[r-l];
}
int c(int l, int k, int r){
return Binom[r-l-1][k-l];
}

Int f(int l, int r){
int &z = dp[l][r]; if (z == -1){
Int zz = 0; FOR(k, l, r) if (op[k] == '*'){
zz += (Int) f(l, k) * f(k+1, r) * c(l, k, r);
}
else if (op[k] == '+'){
zz += (Int) f(l, k) * w(k+1, r) * c(l, k, r);
zz += (Int) w(l, k) * f(k+1, r) * c(l, k, r);
}
else{
zz += (Int) f(l, k) * w(k+1, r) * c(l, k, r);
zz -= (Int) w(l, k) * f(k+1, r) * c(l, k, r);
}
z = zz % MOD;
if (z < 0) z += MOD;
}
return z;
}

//(3+5+7) + (2+4+7)

int main(){

#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif

Fact[0] = 1; FOR(i, 1, N) Fact[i] = Int(Fact[i-1]) * i;

REP(i, N){
Binom[i][0] = 1;
REP_1(j, i) Binom[i][j] = (Binom[i-1][j-1] + Binom[i-1][j]) % MOD;
}

while (~scanf("%d", &n)){
REP(i, n) scanf("%d", &a[i]); scanf("%s", op); memset(dp, -1, sizeof(dp));
REP(i, n) dp[i][i] = a[i];
printf("%d\n", f(0, n-1));
}
}

```

## 1004

```#include <iostream>
#include <cstring>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, a, b) for (int i=a-1;i>=b;--i)
#define RST(A) memset(A, 0, sizeof(A))

typedef long long LL;
const int MOD = int(1e9) + 7;

int pow(int a, int b){
int z = 1;
while (b){
if (b&1) z = (LL)z * a % MOD;
a = (LL)a * a % MOD; b >>= 1;
}
return z;
}

const int N = int(1e2) + 9;
int Fact[N], P[N][N], I[N], II[N]; bool vis[N];
int n, m;

int solve(){
bool bad = false; int d = 0; REP(i, m){
scanf("%d", &P[i][0]);
if (P[i][0] == -1) ++d;
else{
RST(vis); vis[P[i][0]] = true;
FOR(j, 1, n){
scanf("%d", &P[i][j]);
vis[P[i][j]] = true;
}
}
}

if (d){
return pow(Fact[n], d-1);
}
else{
REP(i, n) I[i] = i; DWN(i, m, 0){
REP(j, n) II[j] = I[j];
REP(j, n) I[j] = P[i][II[j]] - 1;
}

REP(i, n) if (I[i] != i) return 0;
return 1;
}
}

int main(){

#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif

Fact[0] = 1; FOR(i, 1, N) Fact[i] = (LL) Fact[i-1] * i % MOD;
while (cin >> n >> m){
cout << solve() << endl;
}
}
```

## 1005

```#include <iostream>
#include <cstring>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define RST(A) memset(A, 0, sizeof(A))

typedef long long LL;

const int N = int(1e5) + 9;
int A[N], L[N], R[N], n, d1, d2;

LL solve(){
LL z = 0;

REP(i, n) scanf("%d", &A[i]);

REP(i, n-1){
if (A[i+1] - A[i] == d1){
L[i+1] = L[i] + 1;
}
else{
L[i+1] = 0;
}
}

R[n-1] = 0;
DWN(i, n-1, 0){
if (A[i+1] - A[i] == d2){
R[i] = R[i+1] + 1;
}
else{
R[i] = 0;
}
}

if (d1 == d2){
/*REP(i, n){
z += (LL)(R[i]+1)*(R[i]+2) / 2;
i += R[i];
}
return z;*/
REP(i, n) L[i] = 0;
}

REP(i, n){
z += (LL) (L[i]+1)*(R[i]+1);
}
return z;
}

int main(){

#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif

while (cin >> n >> d1 >> d2){
cout << solve() << endl;
}
}
```

## 1007

```#include <iostream>
using namespace std;

#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)

const int N = int(1e2) + 9;
int A[N][N];
int n, m;

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, 1};
const char op[] = {'D', 'R', 'U', 'R'};
const int SZ = 4;

void snake(int x, int y, int tx, int ty){
int p = 0; bool flag = true; DO(2*(m-1) - 1){
if (x+dx[p] == tx && y+dy[p] == ty){
flag = false; ++y;
putchar('R');
}
x += dx[p]; y += dy[p]; putchar(op[p]);
++p; if (p == SZ) p = 0;
}
if (flag) putchar('R');
}

int main() {

#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);

#endif

while (cin >> n >> m){

int z = 0; REP(i, n) REP(j, m){
scanf("%d", &A[i][j]);
z += A[i][j];
}

if (n&1){
cout << z << endl;
REP(i, n){
DO(m-1) putchar( (i&1) ? 'L' : 'R');
if (i != n-1) putchar('D');
}
}
else if (m&1){
cout << z << endl;
REP(i, m){
DO(n-1) putchar( (i&1) ? 'U' : 'D');
if (i != m-1) putchar('R');
}
}
else{
int x = 0, y = 1;
REP(i, n) REP(j, m) if ((i+j)&1){
if (A[i][j] < A[x][y]){
x = i, y = j;
}
}
z -= A[x][y];
cout << z << endl;

bool flag = true;
REP(i, n/2){

if (i) putchar('D');

if (flag){

if (x/2 == i){
snake(i*2, 0, x, y);
flag = false;
continue;
}

DO(m-1) putchar('R'); putchar('D');
DO(m-1) putchar('L');
}
else{
DO(m-1) putchar('L'); putchar('D');
DO(m-1) putchar('R');
}

}
}

puts("");
}
}
```
```4 2
1 1
1 1
1 1
1 1

2 4
1 1 1 1
1 1 1 1
```