php网站开发是学什么的,禅城网站建设代理,网站做微信链接,com网站建设来源#xff1a;牛客网
时间限制#xff1a;C/C 1秒#xff0c;其他语言2秒
空间限制#xff1a;C/C 32768K#xff0c;其他语言65536K
64bit IO Format: %lld文章目录题目描述题解#xff1a;代码#xff1a;题目描述 小a终于放假了#xff0c;它想在假期中去一些地方…来源牛客网
时间限制C/C 1秒其他语言2秒
空间限制C/C 32768K其他语言65536K
64bit IO Format: %lld文章目录题目描述题解代码题目描述 小a终于放假了它想在假期中去一些地方游玩现在有N个景点编号为1, 2, \dots N1,2,…N同时小b也想出去游玩。由于一些特殊♂原因他们的旅行计划必须满足一些条件 首先他们可以从这N个景点中任意选几个游玩 设小a选出的景点集合为A小b选的景点集合为B则需要满足 A,B的交集不能为空集A,B不能相互包含(AB也属于相互包含) 注意在这里我们认为(A,B)是无序的即(A,B)和(B,A)是同一种方案 输入描述: 一个整数N表示景点的数量 输出描述: 一个整数表示方案数答案对108 7取模 示例1 输入
3输出
3说明 合法的方案如下 小a(1, 2) 小b (2, 3) 小a(1, 3) 小b (2, 3) 小a(1, 2) 小b (1, 3) 示例2 输入 复制
4输出 复制
30示例3 输入 复制
2输出 复制
0示例4 输入 复制
10000输出 复制
68735934示例5 输入
1输出
0备注: 对于100%的数据1⩽n⩽10 13
题解
解题思路来自 我们整合一下题目的条件可以得到A和B都至少有两个元素且最少有一个相同至少有一个不同 一共n的元素我们可以先选出A的元素然后在A中选一些元素作为公共元素然后在A未选的元素中选择给B 可以得到公式 我们注意到公式中存在除法操作且我们需要mod所以用逆元来算 求逆元的方法
代码
#includeiostream
#includecstdio
using namespace std;
typedef long long ll;
const ll mod1e87;
ll exgcd(ll a,ll b,ll x,ll y)//扩展欧几里得算法
{if(b0){x1;y0;return a; //到达递归边界开始向上一层返回}ll gcdexgcd(b,a%b,x,y);ll y1y; //把x y变成上一层的ll x1x;yx1-(a/b)*y1;xy1;return gcd; //得到a b的最大公因数
}
ll inv(ll a,ll mod){ll x,y;ll gcdexgcd(a,mod,x,y);if(gcd!1)return -1;else return (xmod)%mod;
}
ll poww(ll a,ll b){ll ans1;ll basea%mod;while(b){if(b1)ansans*base%mod;basebase*base%mod;b1;}return ans%mod;
}
//ll inv(ll a,ll mod){
// return poww(a,mod-2);
//}
int main()
{ll n;cinn;
// coutpoww(2,3)endl;ll ans1((poww(4,n)-1)-(poww(3,n1))mod)%mod;ll ans23*poww(2,n-1)%mod;ll ans3inv(2,mod)%mod;cout(ans1*ans3ans2)%mod;return 0;
}
