【PGBattle2023】おせんべい1-3

https://products.sint.co.jp/pg_battle

3完80点で19分くらいでした。せんべい4問目を5分くらい考えてギブアップ。昨年より、かなり簡単だったように思う。
[お知らせ] どうも問題4のテストケースに不備があったようで、4問目の正誤とせんべいの回答時間が審査から除外されるようです。

Q1. せんべい（難易度2）積の符号
N個の数を全部かけたときに、+か-か0か教えて。
N <= 200000

考察
0があったら0だし、負の数が奇数個あったら-。

実装

int main() {
  ll N;
  cin >> N;
  ll m = 0, p = 0, zero = 0;
  rep(i, N) {
    ll a;
    cin >> a;
    if (a < 0)
      ++m;
    else if (a > 0)
      ++p;
    else
      ++zero;
  }

  if (zero > 0) {
    cout << 0 << endl;
  } else {
    if (m % 2 == 0) {
      cout << '+' << endl;
    } else {
      cout << '-' << endl;
    }
  }
}

Q2. せんべい（難易度3）ABCの個数
A,B,C,?で構成された文字列Sが渡される。
?にはABCを任意でいれられるとき、部分文字列"ABC"の個数の期待値を教えて。
|S| <= 200000

?BC

0.333333333334

考察
DP[3][200000] // ABCの文字列, index
で管理。indexを1文字ずつ処理すればよさそう。
答えは、'C'が来た時に、前の文字が'B'かつ、前の前の文字が’A’の期待値を足したものになりそう。
Bがきたときに、前の文字がAの期待値を足しておけばいい。

実装

ld DP[3][200020];  // ABC, ex

int main() {
  cincout();

  string S;
  ll N;
  cin >> S;
  N = S.size();

  ld ans = 0.0;

  rep(i, N) {
    if (S[i] == 'A') DP[0][i] = 1.0;
    if (S[i] == 'B' && i > 0) DP[1][i] += DP[0][i - 1];
    if (S[i] == 'C' && i > 1) DP[2][i] += DP[1][i - 1];
    if (S[i] == '?') {
      DP[0][i] = 1.0 / 3.0;
      if (i > 0) {
        DP[1][i] = DP[0][i - 1] / 3.0;
        DP[2][i] = DP[1][i - 1] / 3.0;
      }
    }
    ans += DP[2][i];
  }
  cout << ans << endl;
}

Q3. せんべい（難易度4）距離 K
N個の整数の数列Aがある。K離れた要素(index iとi+K)を任意にswapできるとき、数列のバリエーションを998244353で割ったあまりで教えて。

10 2
3 1 4 1 5 9 2 6 5 3

3600

考察
自由に動かせるバリエーションがいくつあるか考える。
K=2のときは,index{0,2,4,6,…}と{1,3,5,7}のuniteができる。
K=3のときは3つのuniteができる。
それぞれについて要素数の階上通りのバリエーションがある。

ところが、同じ数字を入れ替えてもバリエーションが増えないので、数字が同じ数だけ、階上通りのバリエーションを除く。

実装

int main() {
  MOD = 998244353;
  COMinit(); // 2項定理のライブラリ。inv[], finv[]の生成
  ll N, K;
  cin >> N >> K;
  vector<ll> A(N);
  for (auto &a : A) cin >> a;
  if (K == 0) { // K = 0のときは変化しないので1パターン
    cout << 1 << endl;
    return 0;
  }

  mint ans = 1;

  rep(k, K) {
    vector<ll> V;
    ll cur = k;
    while (cur < N) {
      V.emplace_back(A[cur]);
      cur += K;
    }
    sort(all(V));
    ans *= fac[V.size()];
    // 同じ値の数だけ階上で割る
    ll cnt = 1;
    rep(i, V.size() - 1) {
      if (V[i] == V[i + 1])
        cnt++;
      else {
        ans *= finv[cnt];
        cnt = 1;
      }
    }
    ans *= finv[cnt];
  }
  cout << ans << endl;
}

Q4. せんべい（難易度6）トリオ
1,2,...,3Nの人がいる。3人チームのコンテストを2回開催する。
1回目は、{1,2,3},{4,5,6},...でメンバーを組む。

2回目は、それぞれ違うメンバーを組む。このとき何通りあるか。
ex N=3のとき、
{(1,4,7), (2,5,8), (3,6,9)}はok
(1,2,4)は1,2が同じメンバーのため不可

答えはMで割った余りを求めて。
1 <= N <= 300
1e8 <= M <= 1e9

考察
N=300はDPだよね。わからない。