BZOJ4475 JSOI2015子集选取（动态规划）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

数据范围过大说明这个题和组合一点关系也没有，答案基本上肯定是a ^b 的形式了。暴力打表感觉不太好写，找到当年的题面发现还有个样例是6 40 401898087，于是暴力找a ^b =401898087的数，发现一组a=64 b=40，可以发现a=2 ⁿ b=k，同时也符合第一组数据，于是就做完了。

可以发现集合中的数字互不影响，对每个数字分别考虑。问题变为在一个全0三角形中填一些1，使得若a _i,j =1，则a _i-1,j =a _i-1,j =1。

容易发现每行为1的一定是一个前缀。设f _i,j 为第i行有j个1的方案数，则f _i,j =Σf _i-1,k (j<=k<=i-1)，f _i,i =1。归纳得f _i,j =2 ^i-j-1 (i>j)。

那么这个填法的数量是2 ^k ，每个数字都有这么多填法，答案即为2 ^nk 。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define P 1000000007

int n,m;

int ksm(int a,int k)

{

    int s=;

    for (;k;k>>=,a=1ll*a*a%P) if (k&) s=1ll*s*a%P;

    return s;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4475.in","r",stdin);

    freopen("bzoj4475.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read();

    cout<<ksm(ksm(,n),m);

    return ;

}