fork download
copy 
  1. // Errichto
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define FOR(i,a,b) for(int i = (a); i <= (b); ++i)
  5. #define RI(i,n) FOR(i,1,(n))
  6. #define REP(i,n) FOR(i,0,(n)-1)
  7.  
  8. const int pot = 1024 * 1024;
  9. const int mod = 1e9 + 7;
  10. const char actg[5] = "ACTG";
  11.  
  12. struct M {
  13. 	int t[4][4];
  14. 	M() { REP(i,4)REP(j,4) t[i][j] = 0; }
  15. 	M operator * (const M & b) const {
  16. 		M ans;
  17. 		REP(i,4)REP(j,4)REP(k,4)
  18. 			ans.t[i][k] = (ans.t[i][k] + (long long) t[i][j] * b.t[j][k]) % mod;
  19. 		return ans;
  20. 	}
  21. } m[2 * pot];
  22.  
  23. void fill(char letter, M & mat) {
  24. 	int c = -1;
  25. 	REP(j, 4) if(actg[j] == letter) c = j;
  26. 	assert(c != -1);
  27. 	REP(i,4) REP(j,4) if(i != j) mat.t[i][j] = 0;
  28. 	REP(j, 4) if(j != c) mat.t[c][j] = 1;
  29. }
  30.  
  31. char sl[pot];
  32.  
  33. int main() {
  34. 	int n, q;
  35. 	scanf("%d%d", &n, &q);
  36. 	scanf("%s", sl);
  37. 	REP(i, pot) REP(j, 4) m[pot+i].t[j][j] = 1;
  38. 	REP(i, n) fill(sl[i], m[pot+i]);
  39. 	for(int i = pot - 1; i >= 1; --i) m[i] = m[2*i] * m[2*i+1];
  40. 	while(q--) {
  41. 		int ii;
  42. 		char z;
  43. 		scanf("%d %c", &ii, &z);
  44. 		ii = pot + ii - 1;
  45. 		fill(z, m[ii]);
  46. 		for(int i = ii / 2; i >= 1; i /= 2)
  47. 			m[i] = m[2*i] * m[2*i+1];
  48. 		int s = 0;
  49. 		REP(i,4) REP(j,4) s = (s + m[1].t[i][j]) % mod;
  50. 		// we need (s - 1) / 3
  51. 		s = (s + mod - 1) % mod;
  52. 		int inv = 333333336;
  53. 		assert(inv * 3LL % mod == 1);
  54. 		s = (long long) inv * s % mod;
  55. 		printf("%d\n", s);
  56. 	}
  57. 	return 0;
  58. }
  59.  
Runtime error #stdin #stdout #stderr 0.12s 135552KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:26: void fill(char, M&): Assertion `c != -1' failed.
https://ideone.com/cdnI9U
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!