题目链接：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}\)，快速幂计算即可， 没卵用的 代码如下
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'|ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll quick_mod(ll a,ll b,ll mod) { ll ans=1; while(b) { if(b&1) { ans=(ans*a)%mod; b--; } a=a*a%mod; b>>=1; } return ans; } ll n,k; int main() { n=read(),k=read(); printf("%lld",quick_mod(2,n*k,1000000007)); } |
Comments | NOTHING