2017.6.4試験問題7 K上昇段
746 ワード
K上昇段
【問題の説明】
nの全配列について、k個の単調な増分シーケンスに分割できる場合、k上昇セグメントと呼ばれる.例えば、配列1 2 4 5 6 3 9 10 7 8は合法的な3上昇0段であり、1 2 4 5 6に分けることができる.3 9 10;7 8この3つの単調な増分シーケンス.与えられた(n,k)ごとに、nのすべてのk上昇セグメントの個数を与えてください.
【入力形式】
入力は1行のみで、n,k(1【出力形式】
nのすべてのk上昇セグメントの個数を出力する.
【例】
K.IN K.OUT
3 2 4
(説明、適合条件の配列は132312213231)
(P.S.第六題は樹状配列で、習ったことがなく、できない.
【問題の説明】
nの全配列について、k個の単調な増分シーケンスに分割できる場合、k上昇セグメントと呼ばれる.例えば、配列1 2 4 5 6 3 9 10 7 8は合法的な3上昇0段であり、1 2 4 5 6に分けることができる.3 9 10;7 8この3つの単調な増分シーケンス.与えられた(n,k)ごとに、nのすべてのk上昇セグメントの個数を与えてください.
【入力形式】
入力は1行のみで、n,k(1
nのすべてのk上昇セグメントの個数を出力する.
【例】
K.IN K.OUT
3 2 4
(説明、適合条件の配列は132312213231)
(P.S.第六題は樹状配列で、習ったことがなく、できない.
var
f:array[0..20,0..20]of int64;
n,k,i,j:longint;
begin
readln(n,k);
f[1,1]:=1;// ( 0)
for i:=1 to n do
begin
f[i,i]:=1;
for j:=1 to i-1 do
f[i,j]:=f[i-1,j]*j+f[i-1,j-1]*(i-j+1);//
end;
writeln(f[n,k]);
end.