4475: [Jsoi2015]子集选取

Time Limit: 1 Sec  Memory Limit: 512 MB

Submit: 363  Solved: 255

[][][]

Description

Input

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

Output

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

Sample Input

2 2

Sample Output

16

HINT

 

Source

 

能看出来的话就是大水题，看不出来可能一直懵逼2333

首先每个元素互不影响，所以可以算出 S={1}的方案之后n次幂即可。

那么S={1}的方案数就是 选出一些A为0，其他的为1，而且任意一个1的右下方不能有0.

画一个图就可以发现，这样的0,1分布只能是从中间一条线分开。

分割点可以一开始在Ak,1的左下方，每次可以向右或者向上移动一个单位，并且总是能k步之后到达边界(也就是分割完成)

所以这部分的答案是 2^k。

所以最后答案直接就是 2^(n*k).

#include
      
       #define ll long long#define ha 1000000007using namespace std;int n,k,x,ans;int main(){	scanf("%d%d",&n,&k);	k=n*(ll)k%(ha-1);	ans=1,x=2;	for(;k;k>>=1,x=x*(ll)x%ha) if(k&1) ans=ans*(ll)x%ha;	printf("%d\n",ans);	return 0;}