前言
准备开一个无限深坑，按序号往后做POJ的题目，尽量记录下来一些想法吧。鶸的挣扎系列了解一下(x
POJ-1001
题目描述
Problems involving the computation of exact values of very large magnitude and precision are common. For example, the computation of the national debt is a taxing experience for many computer systems.
This problem requires that you write a program to compute the exact value of R n where R is a real number ( 0.0 < R < 99.999 ) and n is an integer such that 0 < n <= 25.
Input
The input will consist of a set of pairs of values for R and n. The R value will occupy columns 1 through 6, and the n value will be in columns 8 and 9.
Output
The output will consist of one line for each line of input giving the exact value of R^n. Leading zeros should be suppressed in the output. Insignificant trailing zeros must not be printed. Don’t print the decimal point if the result is an integer.
Sample Input
95.123 12
0.4321 20
5.1234 15
6.7592 9
98.999 10
1.0100 12
Sample Output
548815620517731830194541.899025343415715973535967221869852721
.00000005148554641076956121994511276767154838481760200726351203835429763013462401
43992025569.928573701266488041146654993318703707511666295476720493953024
29448126.764121021618164430206909037173276672
90429072743629540498.107596019456651774561044010001
1.126825030131969720661201
题目大意
其实题意很好理解，就是求R^n，要求高精度。
题目分析
所谓大数的乘方，其实就是大数乘法的叠加，相信大家也有各自的大数加减乘的模板，我这里用的是最近刚刚弄好的利用卷积和FFT的大数乘法模板，但从运算角度会比直接利用数组快一些。
思路也很简单，读取的时候记录小数点的位置，利用乘法的模板计算完毕后，再算出小数点应在的位置，之后再社区小数点后数字里不必要的0
比如1.00^3,读入字符串形式的1.00，在从后往前将其转化为int类型后放在数组里，读入数组的为001形式，从后往前数记录小数点前的字符数为2，于是我们可以知道最后结果中保留小数点应该从后往前放在第2*3=6个数字之前，数组中经过模板计算出的结果应该是0000001，再去掉不必要的前导6个0，最后只输出1.
注意
这个题看起来没什么玄机，但是测试数据非常恐怖，在这里举出几个典型的例子
000.10 1
000000 1
000.00 1
.00000 0
000010 1
这就要求我们在输入的时候处理数据，在输出的时候再处理数据，并且要把这些情况考虑进去，这道题我wa了一个上午才过去QAQ。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
#include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; #define L(x) (1 << (x)) const double PI = acos(-1.0); const int Maxn = 400; double ax[Maxn], ay[Maxn], bx[Maxn], by[Maxn]; char sa[Maxn/2]; int sum[Maxn]; int x1[Maxn],x2[Maxn]; int revv(int x, int bits) { int ret = 0; for (int i = 0; i < bits; i++) { ret <<= 1; ret |= x & 1; x >>= 1; } return ret; } void fft(double * a, double * b, int n, bool rev) { int bits = 0; while (1 << bits < n) ++bits; for (int i = 0; i < n; i++) { int j = revv(i, bits); if (i < j) swap(a[i], a[j]), swap(b[i], b[j]); } for (int len = 2; len <= n; len <<= 1) { int half = len >> 1; double wmx = cos(2 * PI / len), wmy = sin(2 * PI / len); if (rev) wmy = -wmy; for (int i = 0; i < n; i += len) { double wx = 1, wy = 0; for (int j = 0; j < half; j++) { double cx = a[i+j], cy = b[i+j]; double dx = a[i+j+half], dy = b[i+j+half]; double ex = dx * wx - dy * wy, ey = dx * wy + dy * wx; a[i+j] = cx + ex, b[i + j] = cy + ey; a[i+j+half] = cx - ex, b[i+j+half] = cy - ey; double wnx = wx * wmx - wy * wmy, wny = wx * wmy + wy * wmx; wx = wnx, wy = wny; } } } if (rev) { for (int i = 0; i < n; i++) a[i] /= n, b[i] /= n; } } int solve(int a[],int na,int b[],int nb,int ans[]) { int len = max(na, nb), ln; for(ln=0; L(ln)<len; ++ln); len=L(++ln); for (int i = 0; i < len ; ++i) { if (i >= na) ax[i] = 0, ay[i] =0; else ax[i] = a[i], ay[i] = 0; } fft(ax, ay, len, 0); for (int i = 0; i < len; ++i) { if (i >= nb) bx[i] = 0, by[i] = 0; else bx[i] = b[i], by[i] = 0; } fft(bx, by, len, 0); for (int i = 0; i < len; ++i) { double cx = ax[i] * bx[i] - ay[i] * by[i]; double cy = ax[i] * by[i] + ay[i] * bx[i]; ax[i] = cx, ay[i] = cy; } fft(ax, ay, len, 1); for (int i = 0; i < len; ++i) ans[i] = (int)(ax[i] + 0.5); return len; } int main() { int l1,l2,l; int i,n,kase; while(scanf("%s %d",sa, &n) != EOF) { if(n == 0){ printf("1\n"); continue; } kase = 0; int kase2 = 0; memset(sum, 0, sizeof(sum)); l1 = strlen(sa); i = 0; while(sa[i] == '0'){ kase2++; i++; } for(i = 0; i < l1; i++){ if(sa[l1-i-1] == '.'){ kase = i*n; l1--; i--; continue; } x1[i] = sa[l1 - i - 1]-'0'; x2[i] = x1[i]; } l2 = l1; l = l1-1; //默认为去掉小数点的长度 while(n>1){ l = solve(x1, l1, x2, l2, sum); for(i = 0; i<l || sum[i] >= 10; i++){ sum[i + 1] += sum[i] / 10; sum[i] %= 10; } l = i; while(sum[l] <= 0 && l>0) l--; //去除前导0 for(i = 0; i <=l; i++){ x2[i]=sum[i]; } l2 = l+1; n--; } for(int j = 1; j < kase-l; j++){ //小于1的时候输出前导0 if(j == 1) printf("."); printf("0"); } int j = 0; while(x2[j]==0 && j < kase){ //去除小数点后不必要的0 j++; } for(i = l; i >= j ; i--){ if(i+1 == kase) printf("."); putchar(x2[i] + '0'); } putchar('\n'); } return 0; } |
后记
这个题真的是超级坑啊，数据可以说是极其严格了，一个不注意就是wa，希望来者多多注意吧233333333.