[树状数组&&逆元]HDU_3074
这题可以用线段树直接做,保存的节点信息是所有的乘积[模上1000000007之后的],不过线段树不好敲,如果有模板的话,还好.没有模板的话,那么少则30分钟吧.
后来才发现原来可以用树状数组+逆元解决这个问题,当然用树状数组和逆元的话,就需要知道两个问题:
1.乘法符合区间可加性
2.a/b%p <====> c*a%p 其中c是b的逆元
这题就是用了这两条性质,这两条性质想清楚之后,这题就好敲了,当然树状数组的更新和求值就会有一点小小的变化.首先对于每个求区间的乘积的问题.我们可以转化成(get(k2)c)%p[get是树状数组的求值函数,(cget(k1-1))%p=1,也就是c是get(k1-1)的逆元]更新也用到逆元,所以增加一个数组来存每个元素.附代码:
1. /
2. 这题首先可以用线段树做,不过写起来比较麻烦
3. 第二个就是用树状数组做,用树状数组做首先要
4. 知道两个问题:
5. 一 乘法符合区间可加性
6. 二 逆元
7. /
8. #include
9. #include
10. #include
11. #include
12.
13. const int max=50006;//最大值
14. const int64 mod=1000000007;//模数
15.
16. int64 tree[max];//树状数组
17. int64 num[max];//原数组
18.
19. int n,q;
20. void init_tree()
21. {//初始化
22. for(int i=0;i
23. tree[i]=1;
24. }
25. void update(int idx,int64 val)
26. {//更新
27. while(idx<=max)
28. {
29. tree[idx] = (tree[idx](val%mod))%mod;
30. idx += idx -idx;
31. }
32. }
33.
34. int64 get(int idx)
35. {//求值
36. int64 ret=1;
37. while(idx>0)
38. {
39. ret = (tree[idx]ret)%mod;
40. idx -= idx -idx;
41. }
42. return ret%mod;
43. }
44.
45. void ex_gcd(int64 a,int64 b,int64 x,int64 &y)
46. {//扩展欧几里得
47. int64 t;
48. if(0 == b)
49. {
50. x = 1;
51. y = 0;
52. return
53. }
54. ex_gcd(b,a%b,x,y);
55. t = x;
56. x = y;
57. y = t - a/b*y;
58. return
59. }
60. int main(void)
61. {
62. #if 1
63. freopen(“3074.in”,“r”,stdin);
64. freopen(“3074.out”,“w”,stdout);
65. #endif
66. int t,tmp;
67. int type;
68. int64 k1,k2;
69. int64 x,y;
70. int64 a,b;
71. scanf(“%d”,t);
72. while(t–)
73. {
74. init_tree();
75. scanf(“%d”,n);
76. for(int i=1;i<=n;i++)
77. {
78. scanf(“%d”,tmp);
79. num[i]=tmp;
80. update(i,tmp);
81. }
82. #if 0
83. for(int i=1;i<=n;i++)
84. printf(“%I64d %I64d\n”,num[i],tree[i]);
85. #endif
86. scanf(“%d”,q);
87. while(q–)
88. {
89. scanf(“%d%I64d%I64d”,type,&k1,&k2);
90. if(1==type)
91. {//change the k1-th num to k2
92. ex_gcd(num[k1],mod,x,y);
93. x = (x%mod+mod)%mod;//这是必须的
94. update(k1,x);
95. update(k1,k2);
96. num[k1]=k2;
97. #if 0
98. printf(“:::x:::%d\n”,x);
99. #endif
100. }
101. else
102. {
103. a=get(k2);
104. b=get(k1-1);
105. ex_gcd(b,mod,x,y);
106. x = (x%mod+mod)%mod;
107. a = ((a%mod)*(x%mod))%mod;
108. printf(“%I64d\n”,a);
109. }
110. }
111. #if 0
112. printf(“=============\n”);
113. for(int i=1;i<=n;i++)
114. printf(“%I64d %I64d\n”,num[i],tree[i]);
115. #endif
116. }
117. return 0;
118. }
