题目还在寻找中，
hdu 1402 ， 模板题吧，A × B。
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 | /************************************************************************* > File Name: hdu1402.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2015年01月15日 星期四 23时39分23秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <complex> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define eps 1e-8 #define x first #define y second #define MAXN 50005 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; typedef complex<double> cp; const double PI = acos(-1.0); char a[MAXN], b[MAXN]; int N, LA, LB, A[MAXN << 2], B[MAXN << 2]; LL ans[MAXN << 2]; cp A1[MAXN << 2], B1[MAXN << 2], C[MAXN << 2]; void Extend() { N = Max(LA, LB); N = 1 << (int)ceil(log(2.0 * N) / log(2.0) - eps); for (int i = LA; i < N; i ++) A[i] = 0; for (int i = LB; i < N; i ++) B[i] = 0; LA = LB = N; for (int i = 0; i < N; i ++) { A1[i] = cp(A[i], 0.0); B1[i] = cp(B[i], 0.0); } } void change(cp y[], int n) { for (int i = 1, j = n / 2; i < n - 1; i ++) { if (i < j) swap(y[i], y[j]); int k = n / 2; while (j >= k) { j -= k; k /= 2; } if (j < k) j += k; } } void fft(cp a[], int n, int One) { change(a, n); for (int i = 2; i <= n; i <<= 1) { cp wn = cp(cos(One * 2 * PI / i), sin(One * 2 * PI / i)); for (int j = 0; j < n; j += i) { cp w = cp(1.0, 0.0); for (int k = j; k < j + i / 2; k ++) { cp u = a[k], v = w * a[k + i / 2]; a[k] = u + v, a[k + i / 2] = u - v; w = w * wn; } } } } void work() { scanf("%s", b); LA = strlen(a), LB = strlen(b); memset(A, 0, sizeof(A)); memset(B, 0, sizeof(B)); memset(A1, 0, sizeof(A1)); memset(B1, 0, sizeof(B1)); memset(C, 0, sizeof(C)); for (int i = 0; i < LA; i ++) { A[i] = a[i] - '0'; } for (int i = 0; i < LB; i ++) { B[i] = b[i] - '0'; } reverse(A, A + LA), reverse(B, B + LB); Extend(); fft(A1, N, 1); fft(B1, N, 1); for (int i = 0; i < N; i ++) { C[i] = A1[i] * B1[i]; } fft(C, N, -1); for (int i = 0; i < N; i ++) { ans[i] = (LL)ceil(C[i].real() - eps) / N; } LL add = 0; for (int i = 0; i < N; i ++) { ans[i] += add; add = ans[i] / 10; ans[i] %= 10; } while (N > 1 && !ans[N - 1]) { N --; } reverse(ans, ans + N); for (int i = 0; i < N; i ++) { printf("%d", (int)ans[i]); } printf("\n"); } int main() { while (scanf("%s", a) != EOF) { work(); } return 0; } |
hdu 4609
题意：给一些边，问从中选三条边构成三角形的概率。
题解：先求出任选两个边组成的情况，利用FFT加速
，然后，每条边，看有多少不能与其形成三角形的个数。
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 | /************************************************************************* > File Name: hdu4609.cpp > Author: skt > Mail: sktsxy@gmail.com > Created Time: 2015年01月16日 星期五 01时14分10秒 ************************************************************************/ #include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <queue> #include <bitset> #include <algorithm> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <complex> #include <cassert> // #pragma comment(linker,"/STACK:102400000,102400000") using namespace std; #define LL long long #define pb push_back #define mp make_pair #define eps 1e-8 #define x first #define y second #define MAXN 100005 template <typename T> inline T Max(T a, T b) {return a>b?a:b;} template <typename T> inline T Min(T a, T b) {return a<b?a:b;} typedef pair<int, int> PII; typedef vector<int> vi; typedef complex<double> cp; const double PI = acos(-1.0); int T, N, a[MAXN], b[MAXN << 2], M; LL all, res, ans[MAXN << 2]; cp A[MAXN << 2], B[MAXN << 2], C[MAXN << 2]; void Extend() { int n = N; N = 1 << (int)(ceil)(log(2.0 * N) / log(2.0) - eps); for (int i = n + 1; i < N; i ++) b[i] = 0; for (int i = 0; i < N; i ++) { A[i] = cp(b[i], 0.0); B[i] = cp(b[i], 0.0); } } void change(cp y[], int n) { for (int i = 1, j = n / 2; i < n - 1; i ++) { if (i < j) swap(y[i], y[j]); int k = n / 2; while (j >= k) { j -= k; k /= 2; } if (j < k) j += k; } } void fft(cp a[], int n, int One) { change(a, n); for (int i = 2; i <= n; i <<= 1) { cp wn = cp(cos(One * 2 * PI / i), sin(One * 2 * PI / i)); for (int j = 0; j < n; j += i) { cp w = cp(1, 0); for (int k = j; k < j + i / 2; k ++) { cp u = a[k], v = w * a[k + i / 2]; a[k] = u + v, a[k + i / 2] = u - v; w = w * wn; } } } } void work() { memset(b, 0, sizeof(b)); memset(ans, 0, sizeof(ans)); N = res = 0; scanf("%d", &M); for (int i = 1; i <= M; i ++) { scanf("%d", &a[i]); b[a[i]] ++; N = Max(N, a[i] + 1); } sort(a + 1, a + 1 + M); Extend(); fft(A, N, 1); fft(B, N, 1); for (int i = 0; i < N; i ++) { C[i] = A[i] * B[i]; } fft(C, N, -1); for (int i = 0; i < N; i ++) { ans[i] = (LL)ceil(C[i].real() - eps) / N; } while (N > 0 && !ans[N - 1]) { N --; } all = (LL)M * (M - 1) * (M - 2) / 6; for (int i = 1; i <= M; i ++) { ans[a[i] + a[i]] --; } for (int i = 0; i <= N; i ++) { ans[i] /= 2; } for (int i = 1; i <= N; i ++) { ans[i] += ans[i - 1]; } for (int i = 1; i <= M; i ++) { res += ans[a[i]]; } printf("%.7lf\n", 1.0 * (all - res) / all); } int main() { scanf("%d", &T); while (T --) { work(); } return 0; } |
这有一道NTT的题目，十分恶心。。。我试着写了一下，出不了结果，求涛哥指导。http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1258
还是 好长的头文件。。。。。