Mike has many friends. Here are nine of them: Alice, Bob, Carol, Dave, Eve, Frank, Gloria, Henry and Irene.
Mike is so skillful that he can master nn languages (aka. PRogramming languages).
His nine friends are all weaker than he. The sets they can master are all subsets of Mike’s languages.
But the relations between the nine friends is very complex. Here are some clues.
Alice is a nice girl, so her subset is a superset of Bob’s. Bob is a naughty boy, so his subset is a superset of Carol’s. Dave is a handsome boy, so his subset is a superset of Eve’s. Eve is an evil girl, so her subset is a superset of Frank’s. Gloria is a cute girl, so her subset is a superset of Henry’s. Henry is a tall boy, so his subset is a superset of Irene’s. Alice is a nice girl, so her subset is a superset of Eve’s. Eve is an evil girl, so her subset is a superset of Carol’s. Dave is a handsome boy, so his subset is a superset of Gloria’s. Gloria is a cute girl, so her subset is a superset of Frank’s. Gloria is a cute girl, so her subset is a superset of Bob’s.Now Mike wants to know, how many situations there might be. Input The first line contains an integer TT(T≤20T≤20) denoting the number of test cases.
For each test case, the first line contains an integer nn(0≤n≤30000≤n≤3000), denoting the number of languages.
Output For each test case, output ”Case #t:” to represent this is the t-th case. And then output the answer. Sample Input 2 0 2 Sample Output Case #1: 1 Case #2: 1024
解題思路：答案為32的n次方，我也不知道為什么是這個答案，我是看別人的題解才知道的，據說是看出來，我只想說6666. 通過這題我總結了乘法大數算法，令d[i]為一個大數的第i位，從右開始，第一位（個位）為0位，則有大數a,b,的乘積為大數c,c.d[i + j] = a.d[i]*b.d[j];但是這樣之后c的每一位可能大于9，所以需要對每一位進行取余（與10），并且向高位進行進位，直到a.len + b.len。最后從最高位（a.len + b.len)開始向低位判斷，c到底有多少位，注意在重載^運算符時，不要一個一個乘，要用快速冪思想，不然這一題會超時。
#include<bits/stdc++.h>using namespace std;const int maxn = 1e5;class bignum{public: int d[maxn];//每一位 int len;//數的長度 bignum() { memset(d,0,sizeof(d)); } bignum(int x) { int l = 0; memset(d,0,sizeof(d)); while(x) { d[l++] = x%10; x /= 10; } len = l; } bignum Operator * (const bignum &res) const { bignum ans; for(int i = 0; i < this->len; i++) { for(int j = 0; j < res.len; j++) { ans.d[i + j] += d[i]*res.d[j]; } } for(int i = 0; i < this->len + res.len; i++) { ans.d[i + 1] += ans.d[i]/10; ans.d[i] %= 10; } int Len = this->len + res.len; while(Len > 1&&ans.d[Len - 1] == 0) { Len--; } ans.len = Len; return ans; } bignum operator ^ (const int x) const { bignum ans(1); bignum res; res.len = this->len; int term = x; for(int i = 0; i < this->len; i++) { res.d[i] = this->d[i]; } while(term) { if(term&1) ans = ans*res; term >>= 1; res = res*res; } return ans; } void print() { for(int i = len - 1; i >= 0; i--) { printf("%d",d[i]); } printf("/n"); }};int main(){ int T; int Case = 1; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); bignum term(32); term = term^n; printf("Case #%d: ",Case++); term.print(); } return 0;}新聞熱點
疑難解答
