从两端到中间分段，然后累乘即可
#include<bits/stdc++.h> using namespace std; #define mod 998244353 #define maxn 200005 #define ll long long ll n,m,A,b[maxn]; ll Pow(ll a,ll b){ ll res=1; while(b){ if(b%2)res=a*res%mod; b>>=1;a=a*a%mod; } return res; } int main(){ cin>>n>>m>>A; for(int i=1;i<=m;i++)cin>>b[i]; sort(b+1,b+1+m); ll ans=Pow(A,n-2*b[m]); for(int i=1;i<=m;i++){ ll p=Pow(A,b[i]-b[i-1]); ans=ans*((p*(p+1)/2)%mod)%mod; } cout<<ans<<endl; }
转载于:https://www.cnblogs.com/zsben991126/p/10945943.html
