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

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

## 题目描述 ##

![11_282_29.png][]

## 输入 ##

输入包含一行两个整数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));
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10460244.html

[11_282_29.png]: https://lydsy.com/JudgeOnline/upload/201604/11%282%29.png