e209: C(n, k) Again!
標籤 :
通過比率 : 1人/2人 ( 50% ) [非即時]
評分方式:
Special

最近更新 : 2019-05-08 21:23

內容

令 $\color{black}{n,\ k\ (k \le n)}$ 為非負整數,定義 $\color{black}{\displaystyle C^n_k = \frac{n!}{k!(n-k)!}}$,很顯然地,我們可以從組合意義上得知 $\color{black}{C^n_k}$ 也是整數。

想要證明 $\color{black}{\displaystyle \frac{n!}{k!(n-k)!}}$ 是整數,不妨提出 $\color{black}{(n-k)!}$ ,改為證明任意連續 $\color{black}{k}$ 個非負整數的乘積皆能被 $\color{black}{k!}$ 整除。

現在有兩個大小為 $\color{black}{k}$ 的集合 $\color{black}{S = \{x | x \in \mathbb{N},\ 1 \le x \le k\},\ T = \{y | y \in \mathbb{N},\ m \le y \le m + k - 1\}}$。

請在 $\color{black}{S,\ T}$ 間建立若干條「邊」,滿足下列性質:

1. 權重大於 1。

2. 對於所有 $\color{black}{x \in S}$, 其連接的邊權重乘積(沒有邊視為 1)恰為 $\color{black}{x}$ 。

3. 對於所有 $\color{black}{y \in T}$, 其連接的邊權重乘積(沒有邊視為 1)為 $\color{black}{y}$ 的因數。

輸入說明

兩個正整數 $\color{black}{m,\ k (m \le 10^9,\ k \le 10^6)}$。

輸出說明

輸出共有 $\color{black}{k}$ 行。

第 $\color{black}{x}$ 行首先輸出一個非負整數 $\color{black}{d}$,代表 $\color{black}{x(x \in S)}$ 連接 $\color{black}{d}$ 條邊,接著輸出 $\color{black}{d}$ 個數對 $\color{black}{y\ w}$,表示 $\color{black}{x}$ 和 $\color{black}{y \in T}$ 有一條權重為 $\color{black}{w}$ 的邊。數字以空格隔開,行尾不應有多餘空白。

範例輸入
範例輸入 1:
5 4

範例輸入 2:
5 4

範例輸入 3:
1 4
範例輸出
範例輸出 1:
0
1 6 2
1 6 3
1 8 4

範例輸出 2:
0
1 8 2
1 6 3
2 6 2 8 2

範例輸出 3:
0
1 2 2
1 3 3
1 4 4
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 0.5s , <1K
公開 測資點#1 (5%): 0.5s , <1K
公開 測資點#2 (5%): 0.5s , <1K
公開 測資點#3 (5%): 0.5s , <1K
公開 測資點#4 (5%): 0.5s , <1K
公開 測資點#5 (5%): 0.5s , <1K
公開 測資點#6 (5%): 0.5s , <1K
公開 測資點#7 (5%): 0.5s , <1K
公開 測資點#8 (5%): 0.5s , <1K
公開 測資點#9 (5%): 0.5s , <1K
公開 測資點#10 (5%): 0.5s , <1K
公開 測資點#11 (5%): 0.5s , <1K
公開 測資點#12 (5%): 0.5s , <1K
公開 測資點#13 (5%): 3.0s , <1K
公開 測資點#14 (5%): 3.0s , <1K
公開 測資點#15 (5%): 3.0s , <1K
公開 測資點#16 (5%): 3.0s , <1K
公開 測資點#17 (5%): 3.0s , <1K
公開 測資點#18 (5%): 3.0s , <1K
公開 測資點#19 (5%): 3.0s , <1K
提示 :

如果你採用的解法會輸出極大量的數字,可以試著用 printf 代替 cout,或是進一步地優化輸出

測資點 #00 ~ #06: $\color{black}{k \le 5}$。

測資點 #07 ~ #12: $\color{black}{k \le 1000}$。

測資點 #13 ~ #19: $\color{black}{k \le 1000000}$。

 

標籤:
出處:
[管理者:
icube (輸光光)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」