立志用最少的代碼做最高效的表達

---

Alice and Bob like playing games very much.Today, they introduce a new game.

There is a polynomial like this: (a0x⁽²0)+1) * (a1 * x⁽²1)+1)…*(an-1 * x⁽²(n-1))+1). Then Alice ask Bob Q questions. In the expansion of the Polynomial, Given an integer P, please tell the coefficient of the x^P.

Can you help Bob answer these questions?

Input
The first line of the input is a number T, which means the number of the test cases.

For each case, the first line contains a number n, then n numbers a0, a1, … an-1 followed in the next line. In the third line is a number Q, and then following Q numbers P.

1 <= T <= 20
1 <= n <= 50
0 <= ai <= 100
Q <= 1000
0 <= P <= 1234567898765432

Output
For each question of each test case, please output the answer module 2012.

Sample Input
1
2
2 1
2
3
4
Sample Output
2
0

---

解析

題意：輸入$a1?an$，輸入$p$，問輸出$x^p$次方前面的系數(shù)是多少

解析：不難看出是一道規(guī)律推導題。
寫出前三項相乘的結(jié)果：
$(a_0?x+1)?(a_1?x^2+1)?(a_2?x^4+1)=a_0{a}_1{a}_2?x^7+a_1{a}_2?x^6+a_0{a}_2?x^5+a_2?x^4+...$

進而推導出：$x^p$的系數(shù)，就是按二進制位數(shù)取1的位子上相乘的值。

---

#include<bits/stdc++.h> using namespace std; typedef long long gg; gg a[100]; int main() {int T; cin >> T; while(T--) {memset(a, 0, sizeof(a));int n; cin >> n; for(int i = 0; i < n; i++) cin >> a[i];int q; cin >> q;for(int i = 0; i < q; i++) {gg sum = 1, k = 0; //存放結(jié)果 gg p; cin >> p;while(p) {if(p%2 == 1) sum = (sum*a[k])%2012; k++;p /= 2;}cout << sum << '\n'; }}return 0; }

總結(jié)

以上是生活随笔為你收集整理的【解析】Alice and Bob_24行代码AC的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。