某岛

… : "…アッカリ~ン . .. . " .. .
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]);
                if (vis[P[i][j]]) bad = true;
                vis[P[i][j]] = true;
            }
        }
    }
    
    if (bad) return 0;
    
    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