Friends
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 1350 Accepted Submission(s): 634
Problem Description
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 n 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.1. Alice is a nice girl, so her subset is a superset of Bob's.2. Bob is a naughty boy, so his subset is a superset of Carol's.3. Dave is a handsome boy, so his subset is a superset of Eve's.4. Eve is an evil girl, so her subset is a superset of Frank's.5. Gloria is a cute girl, so her subset is a superset of Henry's.6. Henry is a tall boy, so his subset is a superset of Irene's.7. Alice is a nice girl, so her subset is a superset of Eve's.8. Eve is an evil girl, so her subset is a superset of Carol's.9. Dave is a handsome boy, so his subset is a superset of Gloria's.10. Gloria is a cute girl, so her subset is a superset of Frank's.11. 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 T(T≤20) denoting the number of test cases.For each test case, the first line contains an integer n(0≤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
Source
找规律？很容易能想到？反正我没想到。
32的n次方，
首先大数用JAVA写是真鸡儿爽，
import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
BigInteger base = new BigInteger("32");
int t = sc.nextInt();
int n;
int cas = 0;
while (t-- > 0) {
n = sc.nextInt();
System.out.printf("Case #%d: ", ++cas);
System.out.println(base.pow(n));
}
}
}
用C++模拟也可以，
大数模板来一发，
1 /*
2 整数大数
3 int数组实现
4 */
5 #include
6 using namespace std;
7
8 #define MAXN 9999//万进制
9 #define DLEN 4//4位
10
11 class BigNum{
12 //private:
13 public:
14 int a[2000];//可以控制大数位数(500*4)
15 int len;//大数长度
16 public:
17 BigNum(){//构造函数
18 len=1;
19 memset(a,0,sizeof(a));
20 }
21 BigNum(const int);//将int转化为大数
22 BigNum(const char *);//将字符串转化为大数
23 BigNum(const BigNum &);//拷贝构造函数
24 BigNum &operator=(const BigNum &);//重载赋值运算符，大数之间赋值
25
26 BigNum operator+(const BigNum &)const;//大数+大数
27 BigNum operator-(const BigNum &)const;//大数-大数
28 BigNum operator*(const BigNum &)const;//大数*大数
29 BigNum operator/(const int &)const;//大数/int
30
31 BigNum operator^(const int &)const;//幂运算
32 int operator%(const int &)const;//取模
33 bool operator>(const BigNum &)const;//大数与大数比较
34 bool operator>(const int &)const;//大数与int比较
35
36 void print();//输出大数
37 };
38
39 BigNum::BigNum(const int b){//将int转化为大数
40 int c,d=b;
41 len=0;
42 memset(a,0,sizeof(a));
43 while(d>MAXN){
44 //c=d-(d/(MAXN+1))*(MAXN+1);
45 c=d%(MAXN+1);//取出后四位
46 d=d/(MAXN+1);//
47 a[len++]=c;
48 }
49 a[len++]=d;
50 }
51 BigNum::BigNum(const char *s){//将字符串转化为大数
52 int t,k,index,l,i,j;
53 memset(a,0,sizeof(a));
54 l=strlen(s);
55 len=l/DLEN;
56 if(l%DLEN)++len;
57 index=0;
58 for(i=l-1;i>=0;i-=DLEN){
59 t=0;
60 k=i-DLEN+1;
61 if(k<0)k=0;
62 for(j=k;j<=i;++j)
63 t=t*10+s[j]-'0';
64 a[index++]=t;
65 }
66 }
67 BigNum::BigNum(const BigNum &T):len(T.len){//拷贝构造函数
68 int i;
69 memset(a,0,sizeof(a));
70 for(i=0;i 71 a[i]=T.a[i]; 72 } 73 BigNum &BigNum::operator=(const BigNum &n){//重载复制运算符，大数之间赋值 74 int i; 75 len=n.len; 76 memset(a,0,sizeof(a)); 77 for(i=0;i 78 a[i]=n.a[i]; 79 return *this; 80 } 81 82 BigNum BigNum::operator+(const BigNum &T)const{//大数+大数 83 BigNum t(*this); 84 int i,big;//位数 85 big=T.len>len?T.len:len; 86 for(i=0;i 87 t.a[i]+=T.a[i]; 88 if(t.a[i]>MAXN){ 89 ++t.a[i+1]; 90 t.a[i]-=MAXN+1; 91 } 92 } 93 if(t.a[big]!=0)t.len=big+1; 94 else t.len=big; 95 return t; 96 } 97 BigNum BigNum::operator-(const BigNum &T)const{//大数-大数 98 int i,j,big; 99 bool flag; 100 BigNum t1,t2;//t1大的，t2小的 101 if(*this>T){ 102 t1=*this; 103 t2=T; 104 flag=0;//前面的大 105 } 106 else{ 107 t1=T; 108 t2=*this; 109 flag=1;//前面的小 110 } 111 big=t1.len; 112 for(i=0;i 113 if(t1.a[i] 114 j=i+1; 115 while(t1.a[j]==0)++j; 116 --t1.a[j--]; 117 while(j>i)t1.a[j--]+=MAXN; 118 t1.a[i]+=MAXN+1-t2.a[i]; 119 } 120 else t1.a[i]-=t2.a[i]; 121 } 122 while(t1.a[t1.len-1]==0&&t1.len>1){ 123 --t1.len; 124 --big; 125 } 126 if(flag)t1.a[big-1]=-t1.a[big-1];//前面的小，结果为负 127 return t1; 128 } 129 BigNum BigNum::operator*(const BigNum &T)const{//大数*大数 130 BigNum ret; 131 int i,j,up; 132 int temp,temp1; 133 for(i=0;i 134 up=0; 135 for(j=0;j 136 temp=a[i]*T.a[j]+ret.a[i+j]+up; 137 if(temp>MAXN){ 138 //temp1=temp-temp/(MAXN+1)*(MAXN+1); 139 temp1=temp%(MAXN+1); 140 up=temp/(MAXN+1); 141 ret.a[i+j]=temp1; 142 } 143 else{ 144 up=0; 145 ret.a[i+j]=temp; 146 } 147 } 148 if(up!=0)ret.a[i+j]=up; 149 } 150 ret.len=i+j; 151 while(ret.a[ret.len-1]==0&&ret.len>1)--ret.len; 152 return ret; 153 } 154 BigNum BigNum::operator/(const int &b)const{//大数/int 155 BigNum ret; 156 int i,down=0; 157 for(i=len-1;i>=0;--i){ 158 ret.a[i]=(a[i]+down*(MAXN+1))/b; 159 down=a[i]+down*(MAXN+1)-ret.a[i]*b; 160 } 161 ret.len=len; 162 while(ret.a[ret.len-1]==0&&ret.len>1)--ret.len; 163 return ret; 164 } 165 166 BigNum BigNum::operator^(const int &n)const{//幂运算 167 BigNum t,ret(1); 168 int i; 169 if(n<0)exit(-1); 170 if(n==0)return 1; 171 if(n==1)return *this; 172 int m=n; 173 while(m>1){ 174 t=*this; 175 for(i=1;i<<1<=m;i<<=1){ 176 t=t*t; 177 } 178 m-=i; 179 ret=ret*t; 180 if(m==1)ret=ret*(*this); 181 } 182 return ret; 183 } 184 int BigNum::operator%(const int &b)const{//取模 185 int i,d=0; 186 for(i=len-1;i>=0;--i){ 187 d=((d*(MAXN+1))%b+a[i])%b; 188 } 189 return d; 190 } 191 bool BigNum::operator>(const BigNum &T)const{//大数与大数比较 192 int ln; 193 if(len>T.len)return true; 194 else if(len==T.len){ 195 ln=len-1; 196 while(a[ln]==T.a[ln]&&ln>=0)--ln; 197 if(ln>=0&&a[ln]>T.a[ln])return true; 198 else return false; 199 } 200 else return false; 201 } 202 bool BigNum::operator>(const int &t)const{//大数与int比较 203 BigNum b(t); 204 return *this>b; 205 } 206 207 void BigNum::print(){//输出大数 208 int i; 209 printf("%d",a[len-1]); 210 for(i=len-2;i>=0;--i){ 211 printf("%.4d",a[i]);//%.4d代表4位，不够前面补0 212 } 213 printf("\n"); 214 } 215 216 //int main(){ 217 // char str1[]="2",str2[]="22222222222222222222222222222222222222222222"; 218 // int c=2; 219 // //scanf("%s%s",str1,str2); 220 // BigNum a,b,t; 221 // a=BigNum(str1); 222 // b=BigNum(str2); 223 // printf("a=");a.print(); 224 // printf("b=");b.print(); 225 // printf("c=%d\n",c); 226 // printf("\n"); 227 // 228 // t=a+b; 229 // printf("a+b=");t.print(); 230 // t=a-b; 231 // printf("a-b=");t.print(); 232 // t=a*b; 233 // printf("a*b=");t.print(); 234 // t=a/c; 235 // printf("a/c=");t.print(); 236 // printf("\n"); 237 // 238 // t=a^c; 239 // printf("a^c=");t.print(); 240 // t=a%c; 241 // printf("a%%c=");t.print(); 242 // 243 // a>b?printf("a>b\n"):printf("a<=b\n"); 244 // a>c?printf("a>c\n"):printf("a<=c\n"); 245 // 246 // return 0; 247 //} 248 249 int main() 250 { 251 // printf("%.4d\n", 4); 252 // printf("%04d\n", 4); 253 int t; 254 int n; 255 BigNum base = BigNum(32); 256 BigNum ans; 257 int cas = 0; 258 scanf("%d", &t); 259 while (t--) { 260 scanf("%d", &n); 261 //printf("%d\n", (int)pow(32, n)); 262 ans = base ^ n; 263 printf("Case #%d: ", ++cas); 264 ans.print(); 265 //printf("len = %d\n", ans.len * 4); 266 } 267 return 0; 268 } View Code 参考链接
发表评论