# Gori#021(ABC041)

# B - 直方体

# 概要

$A,B,C$ が与えられた時, $A \times B \times C$ を $10^9 + 7$ で割ったあまりを求めよ.

# 解法

問題文に答えが書いてある.

#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;

int main() {
  int64_t a,b,c, ans = 0;
  cin >> a >> b >> c;
  (ans = (a * b % MOD) * c) %= MOD;
  cout << ans << endl;
  return 0;
}

# C - 背の順

# 概要

身長が $a_i$ の生徒が $N$ 人いる.
生徒達を背の順に並べたときの出席番号を出力せよ.

# 解法

std::pairで(身長, 出席番号)を持ち, 身長順をキーとして降順にソートしてから出力すればよい.

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;cin >> n;
  vector< pair<int,int> > a(n);  
  for(int i=0;i<n;++i) {cin >> a[i].first; a[i].second = i+1;}
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  for(int i=0;i<n;++i) cout << a[i].second << endl;
  return 0;
}

# D - 徒競走

# 概要

$N$ 匹のうさぎが徒競走をした.
観客からは, $x_i$ 番目のうさぎは $y_i$ 番目のうさぎよりも先にゴールしたという情報が $M$ 人分与えられる.
ここで, 全ての観客の情報に合致する着順は何通りあるか求めよ.

# 解法

制約からbitDPであることに気づく
まず, DPテーブルの持ち方を考える(以下のようになる)

dp[i][j] := i番目のうさぎまで見たときに,
            状態がj(0:unreached, 1:reached)だったときの通り数

その後, 遷移を考える
$i$ 番目のうさぎが遷移できるのは,
- $i=x_i$ のとき, 状態 $j$ の $yi$ ビット目が立っていないとき
- ( $y_i$ 番目のうさぎは到達していてはならない)
- $i=y_i$ のとき ,状態 $j$ の $x_i$ ビット目が立っているとき
- ( $x_i$ 番目のうさぎは到達していなければならない)
DPテーブルの持ち方と遷移がわかったので解ける
ちなみに計算量は $O(n \times 2^n \times n \times m) = O(n^2 \times 2^n \times m)$

#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define int int64

int dp[20][(1<<20)];
vector< int > e[20];

signed main() {
  int n,m; cin >> n >> m;
  for(int mi=0;mi<m;++mi){
    int x,y;
    cin >> x >> y;
    --x; --y;
    e[x].push_back(y);
  }

  dp[0][0] = 1;
  for(int ni=0;ni<n;++ni){
    for(int state=0;state<(1<<n);++state){
      // i番目のうさぎへの遷移が可能かを確認
      for(int i=0;i<n;++i){
        if(state & (1<<i)) continue;

        bool can_move = true;
        for (auto &&ti: e[i]) {
          can_move &= !(state & (1<<ti));
        }

        if (!can_move) continue;
        dp[ni+1][state | (1<<i)] += dp[ni][state];
      }
    }
  }

  int ans = dp[n][(1<<n)-1];
  cout << ans << endl;
  return 0;
}

以上.
お疲れ様でした.

# Gori#021(ABC041)

# B - 直方体

# 概要

# 解法

# C - 背の順

# 概要

# 解法

# D - 徒競走

# 概要

# 解法

# 参考資料