• API
• FAQ
• Tools
• Archive
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.

Top