当前位置 博文首页 > 文章内容

    [ZJOI2020]传统艺能

    作者: 栏目:未分类 时间:2020-07-09 16:02:47

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    https://www.luogu.com.cn/blog/Thinking/solution-p6630

    #include<bits/stdc++.h>
    using namespace std;
    #define fp(i,l,r) for(register int (i)=(l);i<=(r);++(i))
    #define fd(i,l,r) for(register int (i)=(l);i>=(r);--(i))
    #define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
    #define mem(a) memset((a),0,sizeof (a))
    #define O(x) cerr<<#x<<':'<<x<<endl
    #define int long long
    inline int read(){
    	int x=0,f=1;char ch=getchar();
    	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    	return x*f;
    }
    void wr(int x){
    	if(x<0)putchar('-'),x=-x;
    	if(x>=10)wr(x/10);
    	putchar('0'+x%10);
    }
    const int mod=998244353;
    inline void tmod(int &x){x%=mod;}
    inline int qpow(int a,int b){
    	int res=1;a%=mod;
    	for(;b;b>>=1,tmod(a*=a))
    		if(b&1)tmod(res*=a);
    	return res;
    }
    inline int ginv(int x){return qpow(x,mod-2);}
    struct Mat{
    	int a11,a12,a13,a22,a23;
    	inline Mat operator*(const Mat &b)const{
    		return {a11*b.a11%mod,(a11*b.a12+a12*b.a22)%mod,(a11*b.a13+a12*b.a23+a13)%mod,
    				a22*b.a22%mod,(a22*b.a23+a23)%mod};
    	}
    };
    int ans,inv,n,K;
    inline Mat qpow(Mat a,int b){
    	Mat res={1,0,0,1,0};
    	for(;b;b>>=1,a=a*a)
    		if(b&1)res=res*a;
    	return res;
    }
    void solve(int L,int R,int l,int r){
    	if(L<R){
    		int mid=read();
    		solve(L,mid,L,R);solve(mid+1,R,L,R);
    	}
    	if(!l)tmod(ans+=inv);
    	else{
    		int a=(l*(l-1)+(n-r)*(n-r+1)>>1)%mod,
    			b=(L*(r-R)+(n-R+1)*(L-l))%mod,
    			c=l*(n-r+1)%mod,
    			d=((l+L-1)*(L-l)+(n+n-R-r+1)*(r-R)>>1)%mod;
    		tmod(ans+=qpow({(a+c)*inv%mod,d*inv%mod,b*inv%mod,(a+d)*inv%mod,(b+c)*inv%mod},K).a13);
    	}
    }
    main(){
    	n=read();K=read();inv=ginv(n*(n+1)/2);
    	solve(1,n,0,0);
    	printf("%lld\n",ans);
    	return 0;
    }