北京有哪些著名网站,法库综合网站建设方案,宁波网页设计机构,wordpress邮件配置正题 题目大意
给出nnn#xff0c;求一个长度为2n2n2n的由1∼n1\sim n1∼n各两个组成的一个序列使得有一个数的前缀数量不小于任何数字。 解题思路
首先这个数字肯定是第一个数字#xff0c;这里假设为111#xff0c;那么要求任意位置111的前缀数量都不小于别的数。
也就…正题 题目大意
给出nnn求一个长度为2n2n2n的由1∼n1\sim n1∼n各两个组成的一个序列使得有一个数的前缀数量不小于任何数字。 解题思路
首先这个数字肯定是第一个数字这里假设为111那么要求任意位置111的前缀数量都不小于别的数。
也就是第二个111在任何一个数字的前面我们考虑枚举第二个1的位置iii那么对面该位置前方有nnn个数可以放置方案为P(n,i−2)P(n,i-2)P(n,i−2)。然后对于该位置后方有2∗n−i2*n-i2∗n−i个数可以放置但是有n−i1n-i1n−i1个数字有一个重复所以方案为(2∗n−1)!2n−i1\frac{(2*n-1)!}{2^{n-i1}}2n−i1(2∗n−1)!
所以答案就是n∗∑i2nP(n,i−2)∗(2∗n−1)!2n−i1n*\sum_{i2}^nP(n,i-2)*\frac{(2*n-1)!}{2^{n-i1}}n∗i2∑nP(n,i−2)∗2n−i1(2∗n−1)! codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N2e610,XJQ998244353;
ll n,fac[N],z[N],pows[N],ans;
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%XJQ;xx*x%XJQ;b1;}return ans;
}
int main()
{scanf(%lld,n);fac[0]z[0]pows[0]1;for(ll i1;i2*n;i)fac[i]fac[i-1]*i%XJQ;for(ll i1;in;i)z[i]z[i-1]*(n-i)%XJQ,pows[i]pows[i-1]*2%XJQ;for(ll i2;in1;i){ansz[i-2]*fac[2*n-i]%XJQ*power(pows[n-i1],XJQ-2)%XJQ;ans%XJQ;}printf(%lld,ans*n%XJQ);
}
