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 ;

}

巴特西

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

最新文章

热门文章