题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4475

题意:还是用原图好了...


题很容易找规律水掉,证明还是很神的...

首先,我们用\(F(n,k)\) 来表示对于 n 个元素,边长为 k 时的答案。我们考虑在已知 n-1 的情况下,新加入一个元素 n 对于原来的元素是没有影响的,所以每一个对于元素 n 的新方案都能对应所有的旧方案,所以从 n-1 到 n 的过程的方案数是乘法计算的,那么\(F(n,k)=F(1,k)^n\)...(这段的题解都比较简短,然而蒟蒻看不懂,尝试说的详细一些... 结果貌似更模糊了...)

所以我们考虑如何快速求出\(F(1,k)\)... 同样,考虑在已知前 k-1 行的方案数 (即\(F(1,k-1)\)) 的情况下,现在新加入第 k 行.... 由于一个集合肯定是它左边元素的子集,所以当第 k 行第 j 列的元素为 1 时,它左边的元素必定全是 1,同理,它上面的元素也必定全是 1,那么它左上的元素也必定都是 1... 左边的元素考虑完了,现在考虑右边的元素,很显然,k 行里有且只能有一段从右边开始连续的 1... 那么就右边就都是 0 了...

这样处理后,只有右上方的一个 (k-j-1)*(k-j-1) 的三角形是无法确定的啦,那么就有下式 (记\(F(1,k)\) 为\(F[k]\))....

$$F[k]=\sum_{i=1}^{k}F[k-i]+1$$

归纳可得\(F[k]=2^k\),那么\(ans=2^{kn}\),快速幂计算即可, 没卵用的 代码如下

 


一个非常弱的准退役OIER