ZOJ 3813 Alternating Sum （胡搞）

发表于 | 更新于 | 分类于 ， ， ， ， | 评论数： | 阅读次数：

ZOJ3813 推一下公式，然后分类讨论一下。

Alternating Sum

Time Limit: 2 Seconds Memory Limit: 65536 KB

There is a digit string S with infinite length. In addition, S is periodic and it can be formed by concatenating infinite repetitions of a base string P. For example, if P = 3423537, then S = 3423537342353734235373423537…

Let’s define the alternating sum on substrings of S. Assume Sl..r is a substring of S from index l to index r (all indexes are 1-based), then the alternating sum of Sl..r is:

G(l, r) = Sl - Sl+1 + Sl+2 - … + (-1)r-lSr

For example, S2..10 = 423537342, then G(2, 10) = 4 - 2 + 3 - 5 + 3 - 7 + 3 - 4 + 2 = -3.

Now, you are given the base string P and you have to do many operations. There are only two kinds of operations:

  • 1 x d: set Px to d, d is a single digit.
  • 2 l r: find the sum of G(i, j) that l <= i <= j <= r.

For each second operation, you should output the sum modulo 109 + 7.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains a digit string P (1 <= length(P) <= 100000).

The second line contains an integer Q (1 <= Q <= 100000) indicating the number of operations. Each of the following Q lines is an operation in such format:

  • 1 x d (1 <= x <= length(P), 0 <= d <= 9)
  • 2 l r (1 <= l <= r <= 1018)

Output

For each “2 l r” operation, output an integer, indicating the sum modulo 109 + 7.

Sample Input

2
324242
4
2 1 1
2 1 4
1 3 7
2 3 4
324242
6
2 1 1
1 3 7
2 2 4
1 3 4
2 7 10
2 1 30

Sample Output

3
20
14
3
8
20
870

如果是对于1操作，直接修改就是了，注意把要维护的东西更新一下。   对于2操作。 比如要查询 \[l,r\] 很容易发现，答案其实是  \\(a\_l*(r-l+1)+a\_(l+2)*(r-l+1-2)+a_(l+4)*(r-l+1-4)+........\\) 其实也就是说是从l出发的奇数项是有值的。 而且前面的系数刚好是等差数列。 那么我们需要维护的是， 奇数和偶数项的 \\(a\_i*(n+1-i)\\)的前缀和。 奇数和偶数项的\\(a\_i\\)的前缀和。 明显树状数组已经足矣。   为何这样维护是可以的呢？   因为刚才说的要求的 \[l,r\]区间的，是可以分段的。 首先是首尾的两段，还有中间的很多段。（当然有可能只有一段或者两段） 所以首先找到 l,r所属于的块，也就是  (i+(n-1))/n 对于需要求的第一段，形式明显是要求  \\(a\_i*(r-l+1)+a\_(i+2)*(r-l+1-2)+......\\) 这里加的是 \[i,n\]这一段的了。 这个其实是我们维护了的后缀和。 因为我们可以很快求出 \\a\_i*(n+1-i)+a\_(i+2)*(n+1-i-2)+....\\) 要求的只需要加了  \\(a\_i+a\_(i+2)+....\\)的倍数就可以了。   尾部和 r 同一段的求的方法类似。 至于中间部分。 只需要对 n分奇数和偶数去讨论。 如果n是偶数。 那么一段一段是周期的。 可以用等差数列求和。 如果n是奇数，然么两段两段是周期的，一样可以用等差数列去求和。         最近写代码能力急剧下降！ 尤其是在比赛后期，思路完全乱掉了，经常犯SB错误，sad

#include <stdio.h>

#include

#include

#include

#include

#include <string.h>

#include

#include

#include

#include <math.h>
using namespace std;
const int MAXN = 100010;
const int MOD = 1e9+7;
void Add(long long &a,long long b){
a += b;
if(a >= MOD)a -= MOD;
}
int lowbit(int x){
return x&(-x);
}
struct BIT{
long long c[MAXN];
int n;
void init(int _n){
n = _n;
memset(c,0,sizeof(c));
}
long long sum(int i){
long long s = 0;
while(i > 0){
Add(s,c[i]);
i -= lowbit(i);
}
return s;
}
void add(int i,long long val){
while(i <= n){
Add(c[i],val);
i += lowbit(i);
}
}
}bt0,bt1,bt2,bt3;
int a[MAXN];
char str[MAXN];
int n;
long long getid(long long x){
return (x + n-1)/n;
}
int getpos(long long x){
return (x-1)%n + 1;
}
long long SUM(int pos1,int pos2,long long loc){
long long ans = 0;
long long sum;
if(pos1%2 != pos2%2)pos2–;
if(pos1%2 == 1){
ans = bt0.sum(pos2) - bt0.sum(pos1-1);
sum = bt2.sum(pos2) - bt2.sum(pos1-1);
}
else {
ans = bt1.sum(pos2) - bt1.sum(pos1-1);
sum = bt3.sum(pos2) - bt3.sum(pos1-1);
}
ans = ans + (loc - (n+1-pos1))%MODsum%MOD;
ans = (ans%MOD+MOD)%MOD;
return ans;
}
long long inv(long long a,long long m){
if(a == 1)return 1;
return inv(m%a,m)(m-m/a)%m;
}
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out1.txt”,”w”,stdout);
int T;
scanf(“%d”,&T);
while(T–){
scanf(“%s”,str);
n = strlen(str);
for(int i = 0;i < n;i++)
a[i+1] = str[i] - ‘0’;
bt0.init(n);
bt1.init(n);
bt2.init(n);
bt3.init(n);
for(int i = 1;i <= n;i++){
if(i%2 == 1){
bt0.add(i,a[i](n+1-i));
bt2.add(i,a[i]);
}
else{
bt1.add(i,a[i](n+1-i));
bt3.add(i,a[i]);
}
}
int op;
int x,d;
long long l,r;
int m;
scanf(“%d”,&m);
while(m–){
scanf(“%d”,&op);
if(op == 1){
scanf(“%d%d”,&x,&d);
if(x%2 == 1){
bt0.add(x,-a[x](n+1-x));
bt0.add(x,d(n+1-x));
bt2.add(x,-a[x]);
bt2.add(x,d);
}
else {
bt1.add(x,-a[x](n+1-x));
bt1.add(x,d(n+1-x));
bt3.add(x,-a[x]);
bt3.add(x,d);
}
a[x] = d;
}
else {
scanf(“%lld%lld”,&l,&r);
long long id1 = getid(l);
long long id2 = getid(r);
int pos1 = getpos(l);
int pos2 = getpos(r);
if(id1 == id2){
long long ans = SUM(pos1,pos2,r-l+1);
printf(“%lld\n”,ans);
}
else {
long long ans = 0;
int pos11 = pos1;
int pos12 = n;
if(pos11%2 != pos12%2)pos12–;
ans += SUM(pos11,pos12,r-l+1);
ans = (ans%MOD+MOD)%MOD;
int pos21 = 1;
int pos22 = pos2;
if( ((id2-1)n + 1 - l)%2 != 0 )pos21++;
if(pos22%2 != pos21%2)pos22–;
if(pos21 <= pos22){
ans += SUM(pos21,pos22,r - ((id2-1)n + pos21) + 1);
ans = (ans%MOD+MOD)%MOD;
}
if(id1 < id2-1){
if(n % 2 == 0){
int pos11 = 1;
int pos12 = n;
if( (id1n+1-l)%2 != 0 )pos11++;
if(pos12 % 2 != pos11%2)pos12–;
if(pos11 <= pos12){
long long tmp1 = SUM(pos11,pos12,0);
long long sou = (r - (id1n + pos11) + 1);
sou = (sou%MOD+MOD)%MOD;
long long nn = id2 - id1 - 1;
nn %= MOD;
long long ttt = nn*sou%MOD + nn*(nn-1)%MOD*inv(2,MOD)%MOD*(-n)%MOD;
ttt = (ttt%MOD+MOD)%MOD;
long long s1;
if(pos11%2 == 1)s1 = bt2.sum(pos12) - bt2.sum(pos11-1);
else s1 = bt3.sum(pos12) - bt3.sum(pos11-1);
long long tttt = tmp1*nn%MOD + s1*ttt%MOD;
tttt = (tttt%MOD+MOD)%MOD;
ans = (ans + tttt)%MOD;
}
}
else {
long long idcnt = id2 - id1 - 1;
if((idcnt/2) > 0){
int pos11 = 1;
int pos12 = n;
if((id1n+1-l)%2 != 0)pos11++;
if(pos12%2 != pos11%2)pos12–;
int pos21 = 1;
int pos22 = n;
if(((id1+1)n+1-l)%2 != 0)pos21++;
if(pos22%2 != pos21%2)pos22–;
long long tmp1 = SUM(pos11,pos12,0);
long long tmp2 = SUM(pos21,pos22,-( pos21 + n - pos11 ));

                            long long tmp = tmp1 + tmp2;
                            tmp = (tmp%MOD+MOD)%MOD;
                            long long sou = (r - (id1*n + pos11) + 1);
                            sou = (sou%MOD+MOD)%MOD;
                            long long nn = idcnt/2;
                            nn %= MOD;
                            long long ttt = nn\*sou%MOD + nn\*(nn-1)%MOD\*inv(2,MOD)%MOD\*(-2*n)%MOD;
                            ttt = (ttt%MOD+MOD)%MOD;
                            long long s1,s2;
                            if(pos11%2 == 1)s1 = bt2.sum(pos12) - bt2.sum(pos11-1);
                            else s1 = bt3.sum(pos12) - bt3.sum(pos11-1);
                            if(pos21%2 == 1)s2 = bt2.sum(pos22) - bt2.sum(pos21-1);
                            else s2 = bt3.sum(pos22) - bt3.sum(pos21-1);
                            s1 = (s1 + s2)%MOD;
                            long long tttt = (tmp\*nn%MOD+s1\*ttt%MOD)%MOD;
                            tttt = (tttt%MOD + MOD)%MOD;
                            ans = (ans + tttt)%MOD;
                        }
                        if(idcnt%2 != 0){
                            int pos1 = 1;
                            int pos2 = n;
                            if( ((id2-2)*n + 1-l)%2 != 0 )pos1++;
                            if(pos2%2 != pos1%2)pos2--;
                            if(pos2 >= pos1){
                                ans += SUM(pos1,pos2,r - ((id2-2)*n + pos1) + 1);
                                ans = (ans%MOD+MOD)%MOD;
                            }
                        }
                    }
                }
                printf("%lld\\n",ans);
            }
        }
    }
}
return 0;

}

------ 本文结束------
  • 本文作者： kuangbin
  • 本文链接： 373.html
  • 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%