BZOJ4475 子集选取

题解

此题正解是找规律
答案很好猜,就是 $2^{nk}$
思考推导过程
一个重要的技巧: 我们用二进制串表示一个子集,那么我们发现每一位都是相互独立的,且贡献只需要乘法原理乘起来就可以了
现在题目变成如果在 $\frac{(k+1)k}{2}$ 个位置上填 $0,1$ ,如果 $(i,j-1),(i-1,j)$ 都是 $1$ ,那么 $(i,j)$ 可 $1$ 可 $0$ ,否则只能填 $0$ ,求方案数

设方案数为 $f[k]$ ,那么答案就是 $(f[k])^n$
首先 $f[0]=1$
我们枚举第 $k$ 行的 $1$ 怎么填的。设 $j$ 为 $1$ 填在第 $k$ 行的第几个位置,那么 $j=[0,k]$ 。首先如果 $j=k$ ,那么显然方案数为 $1$ ;否则如果在 $j$ 填了 $1$ ,那么原来这个前缀以上的部分都只能填 $1$ ,而剩下一个 $k’=i-j-1$ 大小的三角形方案任意,也就是 $f[i-j-1]$ ,那么 $f[k]=f[k-1]+f[k-2]+…+f[0]+1$ ,数学归纳可知$f[k]=2^k$ ,所以答案就很显然了

代码

#define MOD 1000000007
typedef long long ll;

ll N, K;

inline ll quick_pow (ll x, ll p) {
    ll ans = 1;
    while (p) {
        if (p & 1) (ans *= x) %= MOD;
        (x *= x) %= MOD;
        p >>= 1;
    }
    return ans % MOD;
}

int main () {
    read(N), read(K);
    printf("%lld\n", quick_pow(2LL, N * K));
    return 0;
}

引用资料

FYT 的讲课资料

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注