Search

Computer House Random
Computer House Random
  • Randomについて
  • ブログ
  • Project
  • 作品紹介
  • 部員紹介

ARC120-F解説

ARC120 F

pngn
2021/05/25

問題文

出典 ARC120 F

方針

まず,N本のワインからK本連続しないように取る総数は$\binom{N-K+1}{K}$ですね.これは選ぶワインをoとし,選ばれなかったワインをxとすると,先頭K-1本はoxをセットで考えると分かりますね.これを$f(N, K)$と書きます.

すると,i番目を取る総数はfの畳み込みの形で表されます.FFTなどを考えますが,恐らく2変数の畳み込みが必要でかなり厳しい気持ちになります.二項係数のsumはキレイな形の場合二項係数になる場合があります.が,今回sumの添字が中途半端なのでうまくいきません.多分.なのでこの方針から離れることにします.

初等的な組み合わせ論の方針を考えます.必ず取るものがi番目で,それが真ん中のあたりにある時,

……xox……

みたいな形になりますね.……の部分に着目すると,左側の……の一番右と右側の……の一番左は同時にoでも良いことを除くと元の問題とそんなに変わっていない気がします.これはxox部分をxに変えたものの総数と等しいです.

……x……

これはどうやって数えればよいかというと,真ん中のxの位置に何が来てもいいものの総数から真ん中の位置にoがあるものを引けばいいですね.

……(o or x)…… - ……o……

この左の項はN-2個からK-1個のoを選ぶ問題で,右の項はN-2個からi-1番目を必ず取るようにしてK-1個選ぶ総数になります.

N個あってi番目を選ぶという条件のもとでK個取る総数を$g(N, i, K)$と書くと

$$ g(N, i, K) = f(N-2, K-1) - g(N-2, i-1, K-1) $$

みたいな式になります.fはiに関わらず同じなのでなんかうまくいきそうな気配がしますね.

最初にiが真ん中のあたりにあるって条件を書きましたが,もし$i=0, 1$のとき

$$g(N, 0, K) = f(N-2, K-1)$$

$$g(N, 1, K) = f(N-3, K-1)$$

になるので注意が必要です.あと,iは簡単のため端からの距離として定義しておきます.これは左右対称なのでOKです.iは$\min(i, N-1-i)$とすれば良いです.

ソースの中ではfを交互に正負を逆転させ累積和を取る関数をhとし,$i=1$に到達した時の正負を含めて計算する関数をlとしています.lはオーバーしているかの判定をしていないですが,オーバーしている時は二項係数が0になるのでうまくいきます.

ソースコード

#include<cstdio>
using namespace std;

typedef long long ll;
const ll NCK_MAX = 510000;
const ll mod = 998244353;

ll *fac, *finv, *inv;

void nCk_init(ll mod) {
  fac = new ll[NCK_MAX];
  finv = new ll[NCK_MAX];
  inv = new ll[NCK_MAX];
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (ll i = 2; i < NCK_MAX; i++) {
    fac[i] = fac[i-1] * i % mod;
    inv[i] = mod - inv[mod%i] * (mod / i) % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}

ll nCk(ll n, ll k, ll mod) {
  if (fac == NULL) nCk_init(mod);
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}

ll n, k, d, a[300000], dp[300001], ans;

ll f(ll n, ll i) {
  return nCk(n-i+1, i, mod);
}

ll h(ll i) {
  if (i <= 1) return 0;
  if (dp[i] != 0) return dp[i];
  ll tmp = f(n-2*(i-1), k-(i-1));
  if (i % 2 == 1) tmp = mod - tmp;
  return dp[i] = (tmp + h(i-1)) % mod;
}

ll l(ll x) {
  ll tmp = f(n-2*x-1, k-x);
  if (x % 2 == 0) tmp = mod - tmp;
  return tmp;
}

ll g(ll x) {
  return h(x) + l(x);
}


int main() {
  scanf("%lld", &n);
  scanf("%lld%lld", &k, &d);
  for (ll i = 0; i < n; i++) scanf("%lld", &a[i]);
  ll sum = 0;
  for (ll i = 0; i < n; i++) {
    ll x = 2 * i < n ? i : n - 1 - i;
    if (x == 0) {
      ans += f(n-2, k-1) * a[i] % mod;
    } else {
      ans += g(x) * a[i] % mod;
    }
  }
  printf("%lld\n", ans % mod);
}

感想

無限に頭がバグります.解法ガチャでいい方針を引かないと地獄だと思いました.

コンテスト中に通したかったなぁ…

競技プログラミング 記事を共有
Avatar
pngn

AtCoder黄色/スマホアプリやWebの開発やパソコンの勉強が趣味

Computer House Random はパソコンによる創作活動を行っている大阪府立大学の部活動です

Avatar
pngn

AtCoder黄色/スマホアプリやWebの開発やパソコンの勉強が趣味

競技プログラミング 記事を共有

News

ICPC2020参加記

ICPC
pngn
2021/05/08

コンピュータハウスランダムってどんな部活?

【1日目】5分でわかるランダムのこと
NEGI
最終更新 2020/04/18

はじめまして、らんだむちゃんです!

自己紹介と最初の動画
らんだむちゃん
最終更新 2020/03/19

作品紹介

【18日目】難波駅構内をblenderで再現してみた

途中経過
うっかり侍
2021/08/31

【17日目】ウィルダネスアドベンチャー(?)

いつかリベンジする
クマイザサ
最終更新 2021/08/30

【16日目】CHICKEN NIGHTS

正直、すまんかった
Marcus
最終更新 2021/08/29

Tag Cloud

作品紹介 (48) 新歓ブログリレー2021 (46) 新歓ブログリレー2020 (37) 競技プログラミング (34) 新歓ブログリレー2022 (33) 雑談 (32) ゲーム (30) ゲーム制作 (24) 競プロ勉強会 (22) 作品展示リレー2021夏 (19)

最新の投稿

【38日目】OneDriveでファイルを管理して授業や部活で活用しよう!

オム大、クラウド1TBくれるってよ
Kwang
最終更新 2022/04/29

【37日目】受けループやらメタビートやらのすゝめ

(ゲームにおいては)人の嫌がることをするのが最も楽しい
クマイザサ
2022/04/28

【36日目】マイクラのMODパックで遊ぼう

MODパックの導入は難しそうって思ってない?
neuron
2022/04/27

【35日目】大阪公立大学 中百舌鳥図書館利用のススメ

かなり長め
Rikky
2022/04/26
READ MORE

関連記事


ICPC2020参加記

ICPC

Avatar

主客転倒について

コストの寄与を考える

Avatar

AHCに参加してみた。

競プロ勉強

Avatar

競プロのすすめ

そろそろ復帰したい

Avatar

ABC186~195のA~Dまで必要な知識を調べてみた。

競技プログラミング

Avatar

競プロ成長録的なもの

精進しよう

Avatar

Random
Randomについて
ライセンス
Privacy Policy
お問い合わせ
部員専用サイト
Project
新入生向けブログリレー2022
作品展示リレー2021夏
競プロ勉強会
Web
らんだむちゃん
ブログ
作品紹介
LT会
グラフィック
DTM
タグ一覧
Copyright © 2020 Computer House Random
引用
コピー ダウンロード