UVa 13035 - Another Combination Problem

Source

A Bangladeshi Contest at SUST(20151212)
UVa 13035

問題概要

$N$ 個の箱があって,$i$ 番目の箱には $i+1$ 個の玉が入っている.
全ての玉は色が異なる.
箱を $1$ つ選び,その箱から $2$ 個の玉を取り出し,片方を右手に,もう一方を左手に持つ.
左右の手にもつ玉のパターンの数は何通りかを $\text{mod}\ 1000000007\ (10^9+7)$ で求める問題.

解法

$i$ 番目の箱を選んだら,$i+1$ 個の中から $2$ つの玉を選び,左右に割り振るから,$(i+1)i$ パターンの方法がある.
よって,答えは
\begin{align*}\sum_{i=1}^N (i+1)i = \sum_{i=1}^N (i^2+i) = \frac{N(N+1)(2N+1)}{6} + \frac{N(N+1)}{2}\end{align*}となる.

C++によるスパゲッティなソースコード

この部分を表示するには表示権限を持つユーザーでログインする必要があります.


Current time: 2017年11月18日04時26分45秒
Last modified: 2015年12月16日01時35分33秒 (by laycrs)
Tags: Competitive_Programming UVa_Online_Judge UVa_Contest_20151212_1
トップページに戻る

Logged in as: unknown user (not login)

ログイン: