题目描述
输入
输入包含一行两个整数 N 和 K,1<=N,K<=10^9
输出
一行一个整数, 表示不同方案数目模 1,000,000,007 的值.
样例输入
2 2
样例输出
16
可以发现对于集合中每个元素的选取都是互不影响的, 设 $f(n,k)$ 为输入 $n,k$ 时的答案, 那么 $f(n,k)=f(1,k)^n$.
我们现在来推导 $f(1,k)$ 的结果: 可以发现 $1$ 的位置一定是连续的, 设 $a_{i}$ 表示第 $i$ 列最后选取到了 $a_{i}$ 行, 若从第 $1$ 列到第 $m$ 列均存在被选取.
那么可以得到结论:$a_{i+1}\le a_{i}(1\le i <m)$.
设 $g[i][j]$ 代表第 $i$ 列最后选取到了第 $j$ 行, 可以得到递推式:$g[i][j]=\sum\limits_{p=j}^{k}g[i-1][p]$.
通过观察可以得到:$g[i][j]=g[i-1][j]+g[i][j+1]$, 这实际上就是一个顺时针旋转了 $45^{\circ}$ 的杨辉三角.
那么加上都不选取的方案数,$f(1,k)=1+\sum g[i][j]=2^k$, 由此可得 $f(n,k)=2^{nk}$.
- #include<set>
- #include<map>
- #include<queue>
- #include<cmath>
- #include<stack>
- #include<vector>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define ll long long
- using namespace std;
- int n,k;
- int mod=1000000007;
- ll quick(ll x,ll y)
- {
- ll res=1;
- while(y!=0)
- {
- if(y%2==1)
- {
- res=(res*x)%mod;
- }
- x=(x*x)%mod;
- y/=2;
- }
- return res%mod;
- }
- int main()
- {
- scanf("%d%lld",&n,&k);
- ll sum=1ll*n*k;
- printf("%lld",quick(2,sum));
- }
来源: http://www.bubuko.com/infodetail-2973137.html