1162. 【普及组模拟赛】最大杂置(set) 

题目描述

       令S为n个元素的集合，则S有2^n-1个子集（除去空集）。现在要你从这2^n-1个子集中选出最多的子集，使这些子集能构成一个杂置。 杂置是指任意两个集合没有包含或被包含的关系。例如对于有3个元素的集合{a,b,c}。 {a,b}，{a,c}，{b,c}可以构成一个杂置，而{a},{b},{a,b}则不能构成一个杂置。

输入

第一行一个t表示包括t组数据，接下来t行每行一个n。

输出

对于每组数据输出最大杂置包含的集合数。结果模12345678。

样例输入

3 1 2 3

样例输出

1 2 3

提示

【数据范围】 30%的数据t<=10。 100%的数据t<=3000，n<=3000。  

啦啦啦啦，就是排列组合，用杨辉三角形表示就好了，啦啦啦啦

 

const maxn=3000; var a:array[0..maxn,0..maxn] of longint; i,j,t,n:longint; begin assign(input,'set.in'); reset(input); assign(output,'set.out'); rewrite(output); readln(t); a[0,0]:=1; fori:=1 to 3000 do begin a[i,0]:=1; forj:=1 to i do a[i,j]:=(a[i-1,j]+a[i-1,j-1]) mod 12345678; end; fori:=1 to t do begin readln(n); writeln(a[n,n div 2]); end; close(input); close(output); end.