小a的旅行计划

来源：牛客网

时间限制：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不能相互包含(A=B也属于相互包含) 注意：在这里我们认为(A,B)是无序的，即(A,B)和(B,A)是同一种方案

输入描述:
一个整数N表示景点的数量
输出描述:
一个整数表示方案数，答案对10⁸ + 7取模
示例1
输入

输出

说明
合法的方案如下：
小a：(1, 2) 小b： (2, 3)
小a：(1, 3) 小b： (2, 3)
小a：(1, 2) 小b： (1, 3)
示例2
输入
复制

输出
复制

示例3
输入
复制

输出
复制

示例4
输入
复制

输出
复制

68735934

示例5
输入

输出

备注:
对于100%的数据1⩽n⩽10 ¹³

题解：

解题思路来自
我们整合一下题目的条件可以得到，A和B都至少有两个元素，且最少有一个相同，至少有一个不同
一共n的元素，我们可以先选出A的元素，然后在A中选一些元素作为公共元素，然后在A未选的元素中选择给B
可以得到公式
在这里插入图片描述
我们注意到公式中存在除法操作，且我们需要mod，所以用逆元来算
求逆元的方法：

代码：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
const ll mod=1e8+7;
ll exgcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法
{if(b==0){x=1;y=0;return a;  //到达递归边界开始向上一层返回}ll gcd=exgcd(b,a%b,x,y);ll y1=y;    //把x y变成上一层的ll x1=x;y=x1-(a/b)*y1;x=y1;return gcd;     //得到a b的最大公因数
}
ll inv(ll a,ll mod){ll x,y;ll gcd=exgcd(a,mod,x,y);if(gcd!=1)return -1;else return (x+mod)%mod; 
}
ll poww(ll a,ll b){ll ans=1;ll base=a%mod;while(b){if(b&1)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod;
}
//ll inv(ll a,ll mod){
//	return poww(a,mod-2);
//}
int main()
{ll n;cin>>n;
//	cout<<poww(2,3)<<endl;ll ans1=((poww(4,n)-1)-(poww(3,n+1))+mod)%mod;ll ans2=3*poww(2,n-1)%mod;ll ans3=inv(2,mod)%mod;cout<<(ans1*ans3+ans2)%mod;return 0;
}