[UVA][math] 1406 - A Sequence of Numbers
You are given a sequence of N integers (each within the range [0, 216 - 1] ) along with P operations and in order to solve this problem you need to process the operations instructed as follows.
There are two kinds of operations that you will be instructed to perform:
- 1) Modification
- - Given a non-negative number T , you need to increase the value of every number in the sequence by T . If the value of any number in the sequence is larger than 216 - 1 after the operation, you should divide its value by 216 and take the remainder as its value;
- 2) Query
- - Given a non-negative number T , query how many numbers in the sequence satisfies the condition that its bitwise and result with 2T is greater than zero.
For simplicity, all you need to do here is to output the sum ( sum < 10, 000, 000, 000 ) of the answers to all queries.
Input
There are multiple test cases in the input file. Each test case starts with one integer N
(N
105)
, the number of integers in the sequence. The following N
line consists of one integer P
(0P216 - 1)
, the value on i
-th line being the value of the i
-th number in the sequence.
Each of the following lines is either of the format ``C delta
"
(0delta)
, meaning that you should increase the value of every number by delta, or ``Q i
"
(0i15)
, meaning that you should calculate the answer
to the query (as explained in the problem description). Every test case
ends with one character `E' on a single line, followed by a blank line.
N = - 1 indicates the end of input file and should not be processed by your program. It is guaranteed that the total number of operations in each test case does not exceed 200,000.
Output
For each test case, print the sum of answers to queries on one separate line in the format as indicated in the sample output.
Sample Input
3 1 2 4 Q 1 Q 2 C 1 Q 1 Q 2 E -1
Sample Output
Case 1: 5
題目描述：
操作有 2 種
1. 把所有數字加上同一個數字
2. 將所有數字與 2^i 作 and 運算後，有多少非零數字
題目解法：
用一个计数器S, 累加当前所有的delta, 第i个数现在为(A[i] + S) mod 65536.每次询问第i位上为1的数的个数, 等价于判断当前所有的数中 mod 2^(i+1) >= 2^i的数的个数.对读入的N个数预处理, 统计mod 2i = j的数的个数, 设Sum[i][j]表示mod 2^i <= j的数的个数.而每次询问 2^i <= (x + S) mod 2^(i+1) <= 2^(i+1)-1的x的个数.而这样的x mod 2^i也一定对应一个连续的区间, 利用Sum[i+1]值可以O(1)回答.预处理的时间复杂度为n*16, 每次询问为O(1).
#include <stdio.h>
#include <string.h>
using namespace std;
int table[16][65536];
int main() {
int n, cases = 0;
char cmd[10];
while(scanf("%d", &n) == 1 && n != -1) {
memset(table, 0, sizeof(table));
long long ret = 0;
int i, j, k, P, T;
for(i = 0; i < n; i++) {
scanf("%d", &P);
for(j = 0; j < 16; j++)
table[j][P%(1<<(j+1))]++;
}
for(i = 0; i < 16; i++) {
for(j = 1; j < 65536; j++)
table[i][j] += table[i][j-1];
}
int S = 0;
while(scanf("%s", cmd) == 1) {
if(cmd[0] == 'E') break;
scanf("%d", &T);
if(cmd[0] == 'C') {
S += T;
S %= 65536;
} else {
i = 1<<T, j = 1<<(T+1);
int sub = 0;// 2^i <= (x+S) mod 2^(i+1) < 2^(i+1)
int l = ((i-S)%j+j)%j, r = j-1;
if(l <= i) {
sub = table[T][l+i-1]- (l ? table[T][l-1] : 0);
} else {
sub = table[T][r] - (l ? table[T][l-1] : 0);
sub += table[T][(l+i-1)%j];
}
ret += sub;
}
}
printf("Case %d: %lld\n", ++cases, ret);
}
return 0;
}