4475: [Jsoi2015]子集选取
Time Limit: 1 Sec Memory Limit: 512 MBSubmit: 363 Solved: 255
[Submit][Status][Discuss]
Description
Input
输入包含一行两个整数N和K，1<=N,K<=10^9
Output
一行一个整数，表示不同方案数目模1,000,000,007的值。
Sample Input
2 2
Sample Output
16
HINT
Source
By 佚名上传
能看出来的话就是大水题，看不出来可能一直懵逼2333
首先每个元素互不影响，所以可以算出 S={1}的方案之后n次幂即可。
那么S={1}的方案数就是 选出一些A为0，其他的为1，而且任意一个1的右下方不能有0.
画一个图就可以发现，这样的0,1分布只能是从中间一条线分开。
分割点可以一开始在Ak,1的左下方，每次可以向右或者向上移动一个单位，并且总是能k步之后到达边界(也就是分割完成)
所以这部分的答案是 2^k。
所以最后答案直接就是 2^(n*k).
#include<bits/stdc++.h>#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;}
[JSOI 2015] 子集选取
原文地址：https://www.cnblogs.com/JYYHH/p/8528546.html