QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#661458 | #5460. Sum of Numbers | afy | WA | 0ms | 3608kb | C++20 | 7.6kb | 2024-10-20 16:20:44 | 2024-10-20 16:20:45 |
Judging History
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'