fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int N=15,M=1010,K=1024,L=26,mod=998244353;
  4. int n,m;
  5. char a[N];
  6. int pre[N],f[M][K],g[K][L],tmp[N],ans[N];
  7. int main(){
  8. 	scanf("%d%d%s",&n,&m,a+1);
  9. 	for(int i=0;i<=(1<<n)-1;i++){
  10. 		pre[0]=0;
  11. 		for(int j=1;j<=n;j++)
  12. 			pre[j]=pre[j-1]+(i>>(j-1)&1);
  13. 		for(int k=0;k<=L-1;k++){
  14. 			tmp[0]=0;
  15. 			for(int j=1;j<=n;j++){
  16. 				if(a[j]=='a'+k) tmp[j]=pre[j-1]+1;
  17. 				else tmp[j]=max(tmp[j-1],pre[j]);
  18. 				g[i][k]+=((tmp[j]-tmp[j-1])<<(j-1));
  19. 			}
  20. 			cout << i << ' ' << g[i][k] << ' ' << k << '\n';
  21. 		}
  22. 	}
  23. 	f[0][0]=1;
  24. 	for(int i=1;i<=m;i++)
  25. 		for(int j=0;j<=(1<<n)-1;j++)
  26. 			for(int k=0;k<=L-1;k++){
  27. 				f[i][g[j][k]]+=f[i-1][j];
  28. 				f[i][g[j][k]]%=mod;
  29. 			}
  30. 	for(int i=0;i<=(1<<n)-1;i++){
  31. 		ans[__builtin_popcount(i)]+=f[m][i];
  32. 		ans[__builtin_popcount(i)]%=mod;
  33. 	}
  34. 	for(int i=0;i<=n;i++) printf("%d ",ans[i]);
  35. }
Success #stdin #stdout 0.01s 5280KB
comments ()
stdin
copy 
3 4
aaa
stdout
copy 
0 1 0
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
0 0 9
0 0 10
0 0 11
0 0 12
0 0 13
0 0 14
0 0 15
0 0 16
0 0 17
0 0 18
0 0 19
0 0 20
0 0 21
0 0 22
0 0 23
0 0 24
0 0 25
1 3 0
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 1 11
1 1 12
1 1 13
1 1 14
1 1 15
1 1 16
1 1 17
1 1 18
1 1 19
1 1 20
1 1 21
1 1 22
1 1 23
1 1 24
1 1 25
2 5 0
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 10
2 2 11
2 2 12
2 2 13
2 2 14
2 2 15
2 2 16
2 2 17
2 2 18
2 2 19
2 2 20
2 2 21
2 2 22
2 2 23
2 2 24
2 2 25
3 7 0
3 3 1
3 3 2
3 3 3
3 3 4
3 3 5
3 3 6
3 3 7
3 3 8
3 3 9
3 3 10
3 3 11
3 3 12
3 3 13
3 3 14
3 3 15
3 3 16
3 3 17
3 3 18
3 3 19
3 3 20
3 3 21
3 3 22
3 3 23
3 3 24
3 3 25
4 1 0
4 4 1
4 4 2
4 4 3
4 4 4
4 4 5
4 4 6
4 4 7
4 4 8
4 4 9
4 4 10
4 4 11
4 4 12
4 4 13
4 4 14
4 4 15
4 4 16
4 4 17
4 4 18
4 4 19
4 4 20
4 4 21
4 4 22
4 4 23
4 4 24
4 4 25
5 3 0
5 5 1
5 5 2
5 5 3
5 5 4
5 5 5
5 5 6
5 5 7
5 5 8
5 5 9
5 5 10
5 5 11
5 5 12
5 5 13
5 5 14
5 5 15
5 5 16
5 5 17
5 5 18
5 5 19
5 5 20
5 5 21
5 5 22
5 5 23
5 5 24
5 5 25
6 5 0
6 6 1
6 6 2
6 6 3
6 6 4
6 6 5
6 6 6
6 6 7
6 6 8
6 6 9
6 6 10
6 6 11
6 6 12
6 6 13
6 6 14
6 6 15
6 6 16
6 6 17
6 6 18
6 6 19
6 6 20
6 6 21
6 6 22
6 6 23
6 6 24
6 6 25
7 7 0
7 7 1
7 7 2
7 7 3
7 7 4
7 7 5
7 7 6
7 7 7
7 7 8
7 7 9
7 7 10
7 7 11
7 7 12
7 7 13
7 7 14
7 7 15
7 7 16
7 7 17
7 7 18
7 7 19
7 7 20
7 7 21
7 7 22
7 7 23
7 7 24
7 7 25
390625 62500 3750 101
https://ideone.com/rh5bEb
language:
C++14 (gcc 8.3)
created:
38 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!