第十五届北京师范大学程序设计竞赛决赛 D. Disdain Chain【思维】

 

disdain

D. Disdain Chain

Time limit: 2000ms

Memory Limit: 262144KB

64-bit integer IO format: %lld      java class name: Main

Submit Status PID: 52503

BNU ACM校队现在有n名队员,对于任意两名队员ij,要么i鄙视j,要么j鄙视i,需要注意的是鄙视关系并不满足传递性,即使i鄙视jj鄙视k,也并不意味着一定有i鄙视k。小Q同学认为,如果有t名不同的队员满足a_1鄙视a_2a_2鄙视a_3、……、a_{t-1}鄙视a_t,那么这就是一条长度为t鄙视链。显然鄙视链越长越不利于团队建设,小Q同学希望你帮他分别算一算有多少种n个人之间的鄙视关系满足最长的鄙视链的长度是1,2,3,...,n

Input

第一行是一个正整数T(leq 6),表示测试数据的组数,

每组测试数据包含一行,只有一个整数n(2 leq n leq7),表示校队的人数。

Output

对于每组测试数据,输出n行,第i行表示最长鄙视链是i的鄙视关系的个数。

Sample Input

1 2

Sample Output

0 2

Hint

对于样例,在队伍只有2名队员的情况下,无论谁鄙视谁,最长鄙视链的长度都是2

手写几组样例不难发现,因为图是完全图,所以无论怎样设定边的方向,其方案中,最短的最长鄙视链的长度也不会小于N(只会等于N),那么结果显而易见,就是2^(n*(n-1)/2);

Ac代码

#include #include using namespace std; int main() {     int t;     scanf("%d",&t);     while(t--)     {         int n;         scanf("%d",&n);         int bian=n*(n-1)/2;         int ans=1;         for(int i=1;i<=bian;i++)         {             ans*=2;         }         for(int i=1;i<=n-1;i++)printf("0n");         printf("%dn",ans);     } }

相关阅读

发表评论