QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#661458#5460. Sum of NumbersafyWA 0ms3608kbC++207.6kb2024-10-20 16:20:442024-10-20 16:20:45

Judging History

你现在查看的是最新测评结果

  • [2024-10-20 16:20:45]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3608kb
  • [2024-10-20 16:20:44]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define deb(...)
#endif
using namespace std;
#define ll long long
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define db double
#define baoliu(x, y) cout << fixed << setprecision(y) << x
#define endl "\n"
#define alls(x) (x).begin(), (x).end()
#define fs first
#define sec second
#define bug(x) (void)(cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl)
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-8;
const double PI = acos(-1.0);
using uint = unsigned;
const int MOD = 998244353;  // NTT模数

// 模加法
int Add(int x, int y) { return (x + y >= MOD) ? x + y - MOD : x + y; }
// 模减法
int Dec(int x, int y) { return (x - y < 0) ? x - y + MOD : x - y; }
// 模乘法
int mul(int x, int y) { return 1ll * x * y % MOD; }
// 快速幂计算
uint qp(uint a, int b) {
    uint res = 1;
    for (; b; b >>= 1, a = mul(a, a))
        if (b & 1)
            res = mul(res, a);
    return res;
}

namespace NTT {
int sz;                          // FFT大小
uint w[2500005], w_mf[2500005];  // 存储预计算的单位根及其乘法因子
// 计算乘法因子
int mf(int x) { return (1ll * x << 32) / MOD; }
// 初始化NTT
void init(int n) {
    for (sz = 2; sz < n; sz <<= 1);
    uint pr = qp(3, (MOD - 1) / sz);
    w[sz / 2] = 1;
    w_mf[sz / 2] = mf(1);
    for (int i = 1; i < sz / 2; i++) {
        w[sz / 2 + i] = mul(w[sz / 2 + i - 1], pr);
        w_mf[sz / 2 + i] = mf(w[sz / 2 + i]);
    }
    for (int i = sz / 2 - 1; i; i--) {
        w[i] = w[i << 1];
        w_mf[i] = w_mf[i << 1];
    }
}
// 前向NTT
void ntt(vector<uint>& A, int L) {
    for (int d = L >> 1; d; d >>= 1) {
        for (int i = 0; i < L; i += (d << 1)) {
            for (int j = 0; j < d; j++) {
                uint x = A[i + j] + A[i + d + j];
                if (x >= 2 * MOD)
                    x -= 2 * MOD;
                ll t = A[i + j] + 2 * MOD - A[i + d + j];
                ll q = t * w_mf[d + j] >> 32;
                int y = t * w[d + j] - q * MOD;
                A[i + j] = x;
                A[i + d + j] = y;
            }
        }
    }
    for (int i = 0; i < L; i++) {
        if (A[i] >= MOD)
            A[i] -= MOD;
    }
}
// 逆NTT
void intt(vector<uint>& A, int L) {
    for (int d = 1; d < L; d <<= 1) {
        for (int i = 0; i < L; i += (d << 1)) {
            for (int j = 0; j < d; j++) {
                uint x = A[i + j];
                if (x >= 2 * MOD)
                    x -= 2 * MOD;
                ll t = A[i + d + j];
                ll q = t * w_mf[d + j] >> 32;
                int y = t * w[d + j] - q * MOD;
                A[i + j] = x + y;
                A[i + d + j] = x + 2 * MOD - y;
            }
        }
    }
    int k = (L & (-L));
    reverse(A.begin() + 1, A.end());
    for (int i = 0; i < L; i++) {
        ll m = -A[i] & (L - 1);
        A[i] = (A[i] + m * MOD) / k;
        if (A[i] >= MOD)
            A[i] -= MOD;
    }
}
}  // namespace NTT

struct bigint {
    vector<int> nums;  // 存储大整数的每一位
    int operator[](const int& k) const { return nums[k]; }
    int& operator[](const int& k) { return nums[k]; }
    int size() { return nums.size(); }
    void push_back(int x) { nums.push_back(x); }
    // 从整数构造大整数
    bigint(int x = 0) {
        do {
            nums.push_back(x % 10);
            x /= 10;
        } while (x);
    }
    // 从字符串构造大整数
    bigint(string s) {
        for (int i = s.size() - 1; i >= 0; i--)
            nums.push_back(s[i] - '0');
        trim();
    }
    // 去掉多余的前导零
    void trim() {
        while (nums.size() > 1 && nums.back() == 0) {
            nums.pop_back();
        }
    }
    // 清空大整数
    void clear() {
        nums.clear();
    }
    // 输入大整数
    friend istream& operator>>(istream& cin, bigint& num) {
        string tnum;
        cin >> tnum;
        num = tnum;
        return cin;
    }
    // 输出大整数
    friend ostream& operator<<(ostream& cout, bigint num) {
        bool start = false;
        for (int i = num.size() - 1; i >= 0; i--) {
            if (!start && num[i] == 0)
                continue;
            start = true;
            cout << num[i];
        }
        if (!start)
            cout << 0;
        return cout;
    }
};

// 比较运算符重载
bool operator<(bigint a, bigint b) {
    if (a.size() != b.size())
        return a.size() < b.size();
    for (int i = a.size() - 1; i >= 0; i--)
        if (a[i] != b[i])
            return a[i] < b[i];
    return false;
}

bool operator>(bigint a, bigint b) {
    return b < a;
}

bool operator<=(bigint a, bigint b) {
    return !(a > b);
}

bool operator>=(bigint a, bigint b) {
    return !(a < b);
}

bool operator==(bigint a, bigint b) {
    return !(a < b) && !(a > b);
}

bool operator!=(bigint a, bigint b) {
    return a < b || a > b;
}

// 大整数加法
bigint operator+(bigint a, bigint b) {
    bigint res;
    res.clear();
    int t = 0;
    int mx = max(a.size(), b.size());
    for (int i = 0; i < mx || t; i++) {
        if (i < a.size()) {
            t += a[i];
        }
        if (i < b.size()) {
            t += b[i];
        }
        res.push_back(t % 10);
        t /= 10;
    }
    res.trim();
    return res;
}

// 大整数减法
bigint operator-(bigint a, bigint b) {
    bigint res(a);
    bigint sub(b);
    int flag = 0;
    int len = res.size();
    while (sub.size() < res.size())
        sub.push_back(0);
    for (int i = 0; i < len; i++) {
        if (res[i] + flag >= sub[i]) {
            res[i] = res[i] + flag - sub[i];
            flag = 0;
        } else {
            res[i] = res[i] + 10 + flag - sub[i];
            flag = -1;
        }
    }
    res.trim();
    return res;
}

void solve() {
    int n, k;
    cin >> n >> k;
    deb(n, k);
    int avg = n / (k + 1);
    int lef = n % (k + 1);
    string s;
    cin >> s;
    s = " " + s;
    string infmx;
    for (int i = 0; i < n; i++) infmx += '9';
    cout << infmx << endl;
    bigint ans(infmx);
    auto cal = [&](vector<bool>& fvis, bigint& res) {
        int cur = 1;
        for (int i = 0; i < k + 1; i++) {
            if (fvis[i] == 1) {
                res = res + bigint(s.substr(cur, avg + 1));
                cur += avg + 1;
            } else {
                res = res + bigint(s.substr(cur, avg));
                cur += avg;
            }
        }
        assert(cur == n + 1);
    };
    for (int i = 0; i < (1 << (k + 1)); i++) {
        if (__builtin_popcount(i) != lef)
            continue;
        vector<bool> vis(k + 1);
        for (int j = 0; j < (k + 1); j++) {
            if ((i >> j) & 1) {
                vis[j] = 1;
            }
        }
        bigint tmp(0);

        cal(vis, tmp);
        // cout << "tmp: " << tmp << endl;
        // cout << "ans: " << ans << endl;
        if (tmp < ans) {
            ans = tmp;
        }
    }
    cout << ans << endl;
}
signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
#ifdef LOCAL
    double starttime = clock();
    // freopen("in.txt", "r", stdin);
    //  freopen("out.txt", "w", stdout);
#endif
    int t = 1;
    cin >> t;
    while (t--) solve();
#ifdef LOCAL
    double endtime = clock();
    cerr << "Time Used: " << (double)(endtime - starttime) / CLOCKS_PER_SEC * 1000 << " ms" << endl;
#endif
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3608kb

input:

2
8 1
45455151
2 1
42

output:

99999999
9696
99
6

result:

wrong answer 1st lines differ - expected: '9696', found: '99999999'