International Collegiate Programming Contest 2019 Latin American Regional Contests Problem K

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<vector>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 #define mem(s,n) memset(s,n,sizeof s);
 9 #define PI acos(-1.0)
10 typedef long long ll;
11 const int maxn=1e5+5;
12 const ll Inf=0x7f7f7f7f;
13 ll a[maxn],b[maxn];
14 char s[maxn];
15 int main()
16 {
17     scanf("%s",s);
18     int tot=0;
19     //cout<<strlen(s)<<endl;
20     for(int i=0;i<strlen(s)-1;i++)
21     {
22         if(s[i]==s[i+1]) continue;
23         else 
24         {
25             a[++tot]=2*i+3;
26             //cout<<tot<<endl;
27         }
28     }
29     b[1]=1;
30     for(int i=1;i<=tot;i++)
31     {
32         for(int j=i+1;j>=1;j--) b[j]=b[j-1];
33         for(int j=1;j<=i+1;j++) b[j-1]-=a[i]*b[j];
34     }
35     ll k=1;
36     if(s[0]==‘H‘&&tot%2) k=-1;
37     if(s[0]==‘A‘&&tot%2==0) k=-1;
38     cout<<tot<<endl;
39     for(int i=1+tot;i>=1;i--)
40     {    
41          if(i==1) 
42            printf("%lld\n",b[i]*k);
43          else 
44            printf("%lld ",b[i]*k);
45           
46     }
47     return 0;
48 }