BZOJ4475[Jsoi2015]子集选取——递推(结论题)-蒲公英云

BZOJ4475[Jsoi2015]子集选取——递推(结论题)

怼烎@ 2022-01-05 15:09 238阅读 0赞

题目描述

输入

输入包含一行两个整数N和K，1<=N,K<=10^9

输出

一行一个整数，表示不同方案数目模1,000,000,007的值。

样例输入

2 2

样例输出

可以发现对于集合中每个元素的选取都是互不影响的，设$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$列有$1$，其中第$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}$的杨辉三角。

那么加上都不选取的方案数为$1$，$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));
}