洛谷P4157 [SCOI2006]整数划分

题意:

从文件中读入一个正整数n(10≤n≤31000)。要求将n写成若干个正整数之和,并且使这些正整数的乘积最大。

思路:

(结论题)把n写成n=2 * p + 3 * q,q尽可能大时这些正整数的乘积最大。此时,p只可能是0、1、2

考虑高精度的问题,用FFT实现快速幂求$3^q$,再乘$2^p$即可

Code:

#include <map>
#include <set>
#include <array>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <iostream>
#include <stdlib.h>
#include <algorithm>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

#define sd(a) scanf("%d", &a)
#define sdd(a, b) scanf("%d%d", &a, &b)
#define slld(a) scanf("%lld", &a)
#define slldd(a, b) scanf("%lld%lld", &a, &b)

const int N = 3e5 + 10;
const int M = 1e6 + 20;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);

int n, m;
ll ans[N];
int rev[N];

struct Complex{
    double x, y;

    Complex(double _x = 0.0, double _y = 0.0){
        x = _x, y = _y;
    }

    Complex operator +(const Complex &b){
        return Complex(x + b.x, y + b.y);
    }

    Complex operator -(const Complex &b){
        return Complex(x - b.x, y - b.y);
    }

    Complex operator *(const Complex &b){
        return Complex(x * b.x - y * b.y, x * b.y + y * b.x);
    }
};

void change(Complex y[], int len){
    
   for(int i = 0; i < len; i ++){
       rev[i] = rev[i >> 1] >> 1;
       if(i & 1) rev[i] |= (len >> 1); 
   }

   for(int i = 0; i < len; i ++){
       if(i < rev[i]) swap(y[i], y[rev[i]]);
   }
}

void fft(Complex y[], int len, int on){
    change(y, len);

    for(int h = 2; h <= len; h <<= 1){
        Complex wn(cos(2 * PI / h), sin(2 * PI * on / h));
        for(int j = 0; j < len; j += h){
            Complex w(1, 0);
            for(int k = j; k < j + h / 2; k ++){
                Complex u = y[k];
                Complex t = w * y[k + h / 2];

                y[k] = u + t;
                y[k + h / 2] = u - t;
                w = w * wn;
            }
        }
    }
    if(on == -1){
        for(int i = 0; i < len; i ++){
            y[i].x /= len;
        }
    }
}

Complex x1[N], x2[N], a[N];
int mid[N];
int len;

//快速幂 void qmi(int b){ while(b){ if(b & 1){ fft(x1, len, 1); fft(a, len, 1); for(int i = 0; i < len; i ++) x1[i] = x1[i] * a[i]; fft(x1, len, -1); fft(a, len, -1); for(int i = 0; i < len; i ++) mid[i] = (int)(x1[i].x + 0.5); for(int i = 0; i < len; i ++){ mid[i + 1] += mid[i] / 10; mid[i] %= 10; } for(int i = 0; i < len; i ++){ x1[i] = Complex(mid[i], 0); } for(int i = 0; i < len; i ++) mid[i] = (int)(a[i].x + 0.5); for(int i = 0; i < len; i ++){ mid[i + 1] += mid[i] / 10; mid[i] %= 10; } for(int i = 0; i < len; i ++){ a[i] = Complex(mid[i], 0); } } fft(a, len, 1); for(int i = 0; i < len; i ++){ a[i] = a[i] * a[i]; } fft(a, len, -1); for(int i = 0; i < len; i ++) mid[i] = (int)(a[i].x + 0.5); for(int i = 0; i < len; i ++){ mid[i + 1] += mid[i] / 10; mid[i] %= 10; } for(int i = 0; i < len; i ++){ a[i] = Complex(mid[i], 0); } b >>= 1; } } void solve() { int num; cin >> num; n = 0, m = 0; while(num % 3 != 0){ num -= 2; n ++; } m = num / 3; len = 1; while(len <= m + 1) len <<= 1; for(int i = 1; i < len; i ++) x1[i] = x2[i] = a[i] = Complex(0, 0); x1[0] = Complex(1, 0); a[0] = Complex(3, 0); if(n == 1) x2[0] = Complex(2, 0); else if(n == 2) x2[0] = Complex(4, 0); else x2[0] = Complex(1, 0); qmi(m); fft(x1, len, 1); fft(x2, len, 1); for(int i = 0 ; i< len; i ++) x1[i] = x1[i] * x2[i]; fft(x1, len, -1); for(int i = 0; i < len; i ++) ans[i] = (int)(x1[i].x + 0.5); for(int i = 0; i < len; i ++){ ans[i + 1] += ans[i] / 10; ans[i] %= 10; } while(ans[len] == 0 && len > 0) len --; cout << len + 1 << "\n"; for(int i = len, j = 0; j < 100 && i >= 0; j ++, i --){ cout << ans[i]; } puts(""); } int main() { #ifdef ONLINE_JUDGE #else freopen("/home/jungu/code/in.txt", "r", stdin); // freopen("/home/jungu/桌面/11.21/2/in9.txt", "r", stdin); #endif ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T = 1; // sd(T); // cin >> T; while (T--) { solve(); } return 0; }

  

上一篇:webview是啥


下一篇:C++高级语言程序设计实验七-中国矿业大学