E: 飞碟解除器
•题目描述
wjyyy在玩跑跑卡丁车的时候，获得了一个飞碟解除器，这样他就可以免受飞碟的减速干扰了。
飞碟解除器每秒末都会攻击一次飞碟，但每次只有p/q的概率成功攻击飞碟。当飞碟被成功攻击时，减速状态解除。
如果攻击失败，飞碟会使wjyyy的平均速度变为前一秒的1/k倍。
wjyyy一开始以v m/s的速度行驶，问在减速状态解除时，他期望的行驶距离对998244353取模的结果。
输入
输入共一行，共4个非负整数k,p,q,v。其中gcd(p,q)=1。
输出
输出共一行，表示wjyyy的期望行走距离对998244353取模的结果。
样例输入
2 2 3 9
样例输出
119789331
提示
对于100%的数据，gcd(p,q)=1,1≤k≤998244352,1≤p≤q≤998244352,0≤v≤998244352提示wjyyy在第一秒走过的距离是v m，如果他此时没有攻击成功，则在第二秒后走过的距离是2×v/k m。以此类推。
•思路
假设在每秒末飞碟解除
总距离相加得
显而易见(大雾)是一个差比数列前n项和
然后我们就开始高三数学每套试卷都有的错位相减
由于n是趋近于正无穷的所有最后一项的极限为0
所以Sn的极限与等比数列前n项和有关
所以Sn极限为
•代码
View Code
F: gu集合
•题目描述
Dew有一个长为n的集合S。有一天，他想选k个不同的元素出来做游戏。
但是Dew只有两只手，所以他只能先选出k个元素，然后拿出这k个元素中最小的两个。
事实上，Dew更喜欢这k个元素中第二小的那个，因此他会记一个集合T的第二小值为g(T)。此时Dew可以获得c^g(T)!的得分，其中c是一个常数，!表示阶乘。
现在你需要求出Dew从集合S中选出k个元素后，他的期望得分对998244353取模的结果。
输入
输入共两行。
第一行三个正整数n,k,c，分别表示集合S的大小，Dew要选的元素个数，和常数c。
第二行n个互不相同的正整数ai，表示集合S中的元素。保证
。
输出
输出一行一个非负整数，表示 Dew 的期望得分对998244353取模的结果。
样例输入
5 3 2
1 2 3 4 5
样例输出
803628674
•思路
有n个数a1,a2,a3,a4,....(升序排列)，从中选出k个，
总的情况数是C(n,k)种，
其中a2是第二小数的有C(n-2,k-2)个，a2是第二小，肯定得选a1,a2，再从剩下的(n-2)个里选出(k-2)个
其中a3是第二小数的有2*C(n-3,k-2)个,a3是第二小，肯定得选且只能选a1,a2中的一个即两种情况，再从剩下的(n-3)个里选出(k-2)个
其中a4是第二小数的有3*C(n-4,k-2)个,a4是第二小，肯定得选且只能选a1,a2,a3中的一个即三种情况，再从剩下的(n-4)个里选出(k-2)个
...
得到选每个数的情况是
所以被选择的期望然后再乘以阶乘，最终结果为
•细节处理
除法取模：
指数取模：
•代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
const int maxn=5e5+
5;
const int maxnn=1e7+
5;
ll fac[maxn];
ll facc[maxnn];
ll a[maxn];
ll quickMod(ll x,ll y)
{
ll res=
1;
x=x%
mod;
while(y)
{
if(y&
1)
res=res*x%
mod;
x=x*x%
mod;
y>>=
1;
}
return res%
mod;
}
ll getfac()
{
fac[0]=
1;
for(
int i=
1;i<5e5+
5;i++
)
fac[i]=fac[i-
1]*i%
mod;
}
ll getfacc()
{
facc[0]=
1;
for(
int i=
1;i<1e7+
5;i++
)
facc[i]=facc[i-
1]*i%(mod-
1);
}
int main()
{
int n,k,c;
cin>>n>>k>>
c;
getfac();
getfacc();
for(
int i=
1;i<=n;i++
)
cin>>
a[i];
ll ans=
0;
for(
int i=
2;i<=n;i++
)
{
if(n-i<k-
2)
//防止组合数越界
break;
ans=(ans%mod+(i-
1)*fac[n-i]%mod*fac[n-k]%mod*fac[k]%mod*quickMod(fac[n-i-k+
2]*fac[k-
2]%mod*fac[n]%mod,mod-
2)%mod*quickMod(c,facc[a[i]])%mod)%
mod;;
}
cout<<ans<<
endl;
}
View Code
转载于:https://www.cnblogs.com/MMMinoz/p/11200121.html
