SHARE
TWEET

Untitled

a guest Jan 27th, 2019 115 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define mod 998244353
  3. #define maxM 100005
  4.  
  5. using namespace std;
  6.  
  7. int b[maxM],i,j,n,m;
  8. vector <int> ans;
  9.  
  10. vector <int> pomnozi(vector <int> a,int k){
  11. int i;
  12. for(i=1;i<=m;i++){
  13.     a[k+b[i]]=a[k+i];
  14. }
  15. return a;
  16. }
  17.  
  18. vector <int> resi(int s){
  19. int i;
  20. vector <int> ans,tmp;
  21. if(s==0){
  22.     for(i=0;i<=n;i++) ans.push_back(i);
  23.     return ans;
  24. }
  25. ans=tmp=resi(s/2);
  26. for(i=1;i<=n-s/2;i++){
  27.     ans[i+s/2]=tmp[s/2+tmp[i]];
  28. }
  29. if(s%2) ans=pomnozi(ans,s-1);
  30. return ans;
  31. }
  32.  
  33. vector <int> resi1(int s){
  34. int i;
  35. vector <int> ans,tmp;
  36. if(s==0){
  37.     for(i=0;i<=2*m+5;i++) ans.push_back(i);
  38.     return ans;
  39. }
  40. ans=tmp=resi1(s/2);
  41. for(i=tmp.size();ans.size()<=min(n,(m+s)+10);i++){
  42.     ans.push_back(i);
  43.     tmp.push_back(i);
  44. }
  45. for(i=1;i<=min(n,m+s+10)-s/2;i++){
  46.     ans[i+s/2]=tmp[s/2+tmp[i]];
  47. }
  48. if(s%2) ans=pomnozi(ans,s-1);
  49. return ans;
  50. }
  51.  
  52. long long res,c,x;
  53.  
  54. int main()
  55. {
  56.     std::ios_base::sync_with_stdio(false);
  57.     cin>>n>>m;
  58.     for(i=1;i<=m;i++){
  59.         cin>>b[i];
  60.     }
  61.     cin>>c;
  62.     if(n<=500000) ans=resi(n-m+1);
  63.     else ans=resi1(n-m+1);
  64.     x=1;
  65.     for(i=1;i<=n;i++){
  66.        x=(x*c+mod)%mod;
  67.        res=((res+x*ans[i])%mod+mod)%mod;
  68.     }
  69.     cout<<res<<endl;
  70.     return 0;
  71. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top