Round B APAC Test 2017

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

https://code.google.com/codejam/contest/5254487

A. Sherlock and Parentheses

Problem

Sherlock and Watson have recently enrolled in a computer programming course. Today, the tutor taught them about the balanced parentheses problem. A string S consisting only of characters ( and/or ) is balanced if:

It is the empty string, or:
It has the form ( S ) , where S is a balanced string, or:
It has the form S ₁ S ₂ , where S ₁ is a balanced string and S ₂ is a balanced string.

Sherlock coded up the solution very quickly and started bragging about how good he is, so Watson gave him a problem to test his knowledge. He asked Sherlock to generate a string S of L + R characters, in which there are a total of L left parentheses `(` and a total ofR right parentheses `)` . Moreover, the string must have as many different balanced non-empty substrings as possible. (Two substrings are considered different as long as they start or end at different indexes of the string, even if their content happens to be the same). Note that S itself does not have to be balanced.

Sherlock is sure that once he knows the maximum possible number of balanced non-empty substrings, he will be able to solve the problem. Can you help him find that maximum number?

Input

The first line of the input gives the number of test cases, T . T test cases follow. Each test case consists of one line with two integers: L and R .

Output

For each test case, output one line containing Case #x: y , where x is the test case number (starting from 1) and y is the answer, as described above.

其实就是前n项和的求解，不用多说。

B. Sherlock and Watson Gym Secrets

Problem

Watson and Sherlock are gym buddies.

Their gym trainer has given them three numbers, A , B , and N , and has asked Watson and Sherlock to pick two different positive integers i and j, where i and j are both less than or equal to N . Watson is expected to eat exactly i ^A sprouts every day, and Sherlock is expected to eat exactly j ^B sprouts every day.

Watson and Sherlock have noticed that if the total number of sprouts eaten by them on a given day is divisible by a certain integer K , then they get along well that day.

So, Watson and Sherlock need your help to determine how many such pairs of (i, j) exist, where i != j. As the number of pairs can be really high, please output it modulo 10 ⁹ +7 (1000000007) .

Input

The first line of the input gives the number of test cases, T . T test cases follow. Each test case consists of one line with 4 integers A , B , N and K , as described above.

Output

For each test case, output one line containing Case #x: y , where x is the test case number (starting from 1) and y is the required answer.

Limits

1 ≤ T ≤ 100.
0 ≤ A ≤ 10 ⁶ .
0 ≤ B ≤ 10 ⁶ .

Small dataset

1 ≤ K ≤ 10000.
1 ≤ N ≤ 1000.

Large dataset

1 ≤ K ≤ 100000.
1 ≤ N ≤ 10 ¹⁸ .

分析：这题若是暴力求解，一是复杂度为O（N^2）,二是当大数据输入的时候会溢出。这肯定是不行的。

当我们考虑 i ^A % K 时，我们只需考虑 (i%K) ^A % K。i 的范围是[1, N]， i%K 的范围是 [0, K-1]， (i%K) ^A % K 的范围是 [0, K-1]。我们的做法是，分别算出 (i%K) ^A % K 值为0~K-1的个数存入数组sumA[K]， (i%K) ^B % K 值为[0, k-1]的个数存入数组sumB[K]。那么res = sumA[0] * sumB[0] + sumA[1] * sumB[k-1] + sumA[2]*sumB[K-2]+.......就是总的满足条件的（i，j）对数。另外，题目中要求（i， j）不等，所以res还要剔除当（ (i%K) ^A % K + (i%K) ^B % K）% k == 0 的情况。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const double EPS = 1e-;

 const double PI  = acos(-1.0);

 const int INF = 0x3f3f3f3f;

 const LL  MOD = 1e9+;

 template <class T> inline T bigMod(T p, T e, T M){

     long long ret = ;

     for(; e > ; e >>= ){

         if(e & ) ret = (ret * p) % M;

         p = (p * p) % M;

     } return (T)ret % M;    // Attention: bigMod(p, 0, 1), so ret has to module M.

 }

 template <class T> inline T modInverse(T a, T M){return bigMod(a,M-,M);}

 template <class T> inline T gcd(T a, T b){return b ? gcd(b,a%b) : a;}

 LL ar[], Av[], Bv[], sumA[], sumB[];

 int main() {

     ios_base::sync_with_stdio(); cin.tie();

     freopen("C:\\Users\\Administrator\\Desktop\\ClionTest\\B-large-practice.in", "r", stdin);

     freopen("C:\\Users\\Administrator\\Desktop\\ClionTest\\B-large-practice.out", "w", stdout);

     int T; cin >> T;

     for (int ts = ; ts < T + ; ++ts) {

         memset(ar, , sizeof(ar)); memset(sumA, , sizeof(sumA)); memset(sumB, , sizeof(sumB));

         LL A, B, N, K; cin >> A >> B >> N >> K;

         ar[]--;

         for (int i = ; i < K ; ++i) {

             ar[i] += N/K;

             if (i <= (N%K)) ar[i]++;        // ar[i]: 1~N之间，余数为i的个数

             Av[i] = bigMod((LL)i, A, K);    // i^A%K

             Bv[i] = bigMod((LL)i, B, K);    // i^B%K

             sumA[Av[i]] = (sumA[Av[i]] + ar[i]) % MOD;  //余数为Av[i]的个数

             sumB[Bv[i]] = (sumB[Bv[i]] + ar[i]) % MOD;  //余数为Bv[i]的个数

         }

         LL res = ;

         for (int i = ; i < K; ++i) {

             res = (res + sumA[i] * sumB[K-i]) % MOD;    // (i + K - i) % K == 0, 计算个数

         }

         res = (res + sumA[] * sumB[]) % MOD;

         for (int i = ; i < K; ++i) {                   // 剔除(first, second)中first == second的情况

             if ((Av[i] + Bv[i]) % K == ) res = (res + MOD - (ar[i]%MOD)) % MOD;

         }

         printf("Case #%d: %lld\n", ts, res);

     }

     return ;

 }