2020-team1-053

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team1 返回]

== 概述 ==

solved: 7/11  dirt: 13%

rank: 32

[[Image(Rank.png,800px)]]


== 总结 ==

Sakuya：居然打表找出了I题的规律，真是开心啊！

== 题解 ==

A: 观察发现左斜方向的对角线经过的0贡献的块上格子数为2+2，1贡献的块上格子数为1+1+1+1，可以用斜线上的块数量来判断贡献的奇偶性

B: 对于N=L的情况直接polya定理

其余情况打表发现如果L是偶数则任意排列可以互相转换，如果L是奇数则奇排列之间可以互相转换，偶排列之间可以互相转换

polya定理可以推出L奇数答案为 ```\dfrac2{n!}\Large \sum\limits_{2|(n-i)}{n \brack i} k^i=\binom{n+k-1}{n}+\binom{k}{n} ```

L偶数答案为 ```\dfrac1{n!}\Large \sum{n \brack i} k^i=\binom{n+k-1}{n} ```

(第一类斯特林数 n \brack i 是下降幂和正常幂之间的转换系数)

C: 判是否存在欧拉回路。对于1~7，设1向右到2走了x次，可以根据度数关系解出其他所有值，形式如ax+b，因为是解出来的，对每个点出入度数和一定是满足的，需要判的是非负和连通。每个ax+b的形式可以对x解出上界/下界，判一下上界是否不小于下界就可以判是否可以都非负，关于连通，取下界的值带进去求出边数看连不连通，如果不连通且下界<上界，可以取下界+1带进去判，易证只需要验证这两个值就够了。

D: 加入一些边使得图存在过1的欧拉回路且边权和最小。根据题目性质，如果要调整两点的度数，显然加入的是最小生成树上两点的路径。

E:  建议看cjb的wiki

F: 

G: 找性质，发现只有每行全相同或者每列全相同或者全图为大十字时才合法，分开计数即可。

H: 当k包含于j且j包含于i时才对（0，0，0）点有贡献。

I: 场上打表找规律，正解是杨氏矩阵与钩子公式。

J: 

K: 最小数%2=1则先手赢，否则只和总个数有关


https://github.com/ftiasch/icpc-camp-wiki/blob/master/dreadnought/MIPTCamp%202016%20Day3%20-%20Kent%20Nikaido%20Contest%201.page

https://github.com/ftiasch/icpc-camp-wiki/blob/master/new-meta/2017/3/3%20Kent%20Nikaido%20Contest%201.page

[/wiki/2020-team1 返回]

概述

solved: 7/11 dirt: 13%

rank: 32

总结

Sakuya：居然打表找出了I题的规律，真是开心啊！

题解

A: 观察发现左斜方向的对角线经过的0贡献的块上格子数为2+2，1贡献的块上格子数为1+1+1+1，可以用斜线上的块数量来判断贡献的奇偶性

B: 对于N=L的情况直接polya定理

其余情况打表发现如果L是偶数则任意排列可以互相转换，如果L是奇数则奇排列之间可以互相转换，偶排列之间可以互相转换

polya定理可以推出L奇数答案为 ``\dfrac2{n!}\Large \sum\limits_{2|(n-i)}{n \brack i} k^i=\binom{n+k-1}{n}+\binom{k}{n} ``

L偶数答案为 ``\dfrac1{n!}\Large \sum{n \brack i} k^i=\binom{n+k-1}{n} ``

(第一类斯特林数 n \brack i 是下降幂和正常幂之间的转换系数)

C: 判是否存在欧拉回路。对于1~7，设1向右到2走了x次，可以根据度数关系解出其他所有值，形式如ax+b，因为是解出来的，对每个点出入度数和一定是满足的，需要判的是非负和连通。每个ax+b的形式可以对x解出上界/下界，判一下上界是否不小于下界就可以判是否可以都非负，关于连通，取下界的值带进去求出边数看连不连通，如果不连通且下界<上界，可以取下界+1带进去判，易证只需要验证这两个值就够了。

D: 加入一些边使得图存在过1的欧拉回路且边权和最小。根据题目性质，如果要调整两点的度数，显然加入的是最小生成树上两点的路径。

E: 建议看cjb的wiki

F:

G: 找性质，发现只有每行全相同或者每列全相同或者全图为大十字时才合法，分开计数即可。

H: 当k包含于j且j包含于i时才对（0，0，0）点有贡献。

I: 场上打表找规律，正解是杨氏矩阵与钩子公式。

J:

K: 最小数%2=1则先手赢，否则只和总个数有关

https://github.com/ftiasch/icpc-camp-wiki/blob/master/dreadnought/MIPTCamp%202016%20Day3%20-%20Kent%20Nikaido%20Contest%201.page

https://github.com/ftiasch/icpc-camp-wiki/blob/master/new-meta/2017/3/3%20Kent%20Nikaido%20Contest%201.page

附加文件