2018.09.28 牛客网contest/197/C期望操作数(状态转移+前缀和递推)
传送门
比赛手动打了四项感觉有规律,调了40min+之后重新手算了后面几项发现只有前四项满足规律233。
首先这道题只跟q−xq-xq−x有关。
我们尝试找找递推关系。
我们令f[i]f[i]f[i]表示区间左右端点之差为i时的期望步数。
那么显然有:
f[0]=f[0]=f[0]=不存在(方便计算可以看做0)
f[1]=(f[0]+f[1])2+1f[1]=\frac {(f[0]+f[1])} {2}+1f[1]=2(f[0]+f[1])+1
f[2]=(f[0]+f[1]+f[2])3+1f[2]=\frac {(f[0]+f[1]+f[2])} {3}+1f[2]=3(f[0]+f[1]+f[2])+1
…
f[k]=∑i=0kf[i]k+1+1f[k]=\frac {\sum_{i=0} ^kf[i]} {k+1}+1f[k]=k+1∑i=0kf[i]+1
接着我们考虑用前k−1k-1k−1项的前缀和sum[k−1]=absum[k-1]=\frac {a}{b}sum[k−1]=ba来推出f[k]f[k]f[k]和sum[k]sum[k]sum[k]。
显然有:
f[k]=sum[k−1]+f[k]k+1+1f[k]=\frac {sum[k-1]+f[k]} {k+1}+1f[k]=k+1sum[k−1]+f[k]+1
=>f[k]∗k=sum[k−1]+k+1f[k]*k=sum[k-1]+k+1f[k]∗k=sum[k−1]+k+1
带入sum[k−1]=a/bsum[k-1]=a/bsum[k−1]=a/b得出:
f[k]∗k=a+b∗(k+1)bf[k]*k=\frac {a+b*(k+1)}{b}f[k]∗k=ba+b∗(k+1)
=>f[k]=a+b∗(k+1)b∗kf[k]=\frac {a+b*(k+1)}{b*k}f[k]=b∗ka+b∗(k+1)
=>sum[k]=ab+a+b∗(k+1)b∗ksum[k]=\frac {a}{b}+\frac {a+b*(k+1)}{b*k}sum[k]=ba+b∗ka+b∗(k+1)
=>sum[k]=(k+1)∗(a+b)b∗ksum[k]=\frac {(k+1)*(a+b)}{b*k}sum[k]=b∗k(k+1)∗(a+b)
由于答案要用逆元,因此我们维护两个前缀数组a[],b[]a[],b[]a[],b[],用a[i]b[i]\frac{a[i]}{b[i]}b[i]a[i]来表示sum[i]sum[i]sum[i]就行了。
于是线性递推出a,ba,ba,b数组就ok了。
注意并不能用线性筛逆元,并且需要时刻维护a,ba,ba,b数组是小于modmodmod的。
p.s.可以用数论知识来证明a,ba,ba,b的取模对答案没有影响,这里就不证了。
代码:
#include<bits/stdc++.h>
#define ll long long
#define mod 998244353
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
inline ll ksm(ll x,int p){
ll ret=1;
while(p){
if(p&1)ret=ret*x%mod;
x=x*x%mod,p>>=1;
}
return ret;
}
ll a[10000005],b[10000005];
int main(){
a[0]=0,b[0]=1;
for(int i=1;i<=10000000;++i)a[i]=(a[i-1]+b[i-1])*(i+1)%mod,b[i]=b[i-1]*i%mod;
int T;
scanf("%d",&T);
while(T--){
ll l=read(),r=read(),tmp=r-l;
if(!tmp){puts("0");continue;}
printf("%lld\n",(a[tmp-1]+b[tmp-1]*(tmp+1)%mod)%mod*ksm((b[tmp-1]*tmp%mod),mod-2)%mod);
}
return 0;
}
最新文章
- app上线具体流程
- linux命令:chmod
- Web开发必知的八种隔离级别
- arm上的参数列表传递的分析(以android为例)
- 解决Visual Studio 2010/2012的RC4011 warnings
- linux 输入java 出现中文乱码
- APKTool 提取APK文件的资源
- VS2010中编写宏添加作者信息与函数注释
- hdu_2899_Strange fuction(三分查找)
- 第十七章:Python の Web开发基础(四) MVC与Django
- OSM数据下载地址
- laravel5.4生成验证码
- js基础复习点
- 模块2 hashlib;configparser; logging;
- beta冲刺5/7
- go语言关键字图示
- 计算2个时间之间经过多少Ticks
- Android数据存储之SD卡
- sass的多种用法
- 读取web外的配置文件