【超大数据】数字的拆分——int128数据类型的使用方法
题目描述:
将数字 进行拆分为正整数和的形式,拆分出来的数字可以重复使用。问:一共有多少种折分方式?
输入格式:
每一行给出一个数字 , 。整个测试以 代表结束.
输出格式:
拆分的种数。
输入数据 1
3
500
1000
0
输出数据 1
3
2300165032574323995027
24061467864032622473692149727991
说明: ,共 种。
思路分析:
题目本身很简单,直接用动态规划dp即可。状态转移方程为:
只是对于数据范围最大到1000,且题目没有要求取模,这个方案远远超过long long的范围。之前用字符串手工操作进行加减法来计算,超时了。因为题目没有具体说明有多少组测试,最后没办法想到了非常另类的大整数__int128
类型求解,因标准的C++库不直接支持该类型,需要手动重载__int128
类型的输入输出运算符。
- 输入运算符>>重载函数
,
并解析为__int128
整数
istream &operator>>(istream &is, __int128 &num) {
string s;
is >> s; //从输入流中读取一个字符串
num = 0;
for (char c : s) {
if (c >= '0' && c <= '9') {
num = num * 10 + c - '0';//将字符转换为数字并累加到num中
}
}
return is;
}
-
输出运算符<<重载函数,将
__int128
整数转换为字符串,并将其写入输出流ostream &operator<<(ostream &os, __int128 num) { if (num == 0) { return os << "0"; } string s; while (num > 0) { s.push_back('0' + num % 10);//取出num的最后一位数字并添加到字符串中 num /= 10; //去掉num的最后一位数字 } reverse(s.begin(), s.end());//反转字符串以得到正确的数字顺序 return os << s; //输出字符串 }
注意:当前代码没有处理负数、非数字字符或空白字符,但对于本题关系不大。
***只是对于__int128
整数初步探索,对于题解方法不必在意,仅供学习~~,谢谢!***
AC代码:
#include <bits/stdc++.h>
using namespace std;
// 自定义 __int128 的输入输出
istream &operator>>(istream &is, __int128 &num) {//int128重载输入
string s;
is >> s; //从输入流中读取一个字符串
num = 0;
for (char c : s) {
if (c >= '0' && c <= '9') {
num = num * 10 + c - '0';//将字符转换为数字并累加到num中
}
}
return is;
}
ostream &operator<<(ostream &os, __int128 num) {//int128重载输出
if (num == 0) {
return os << "0";
}
string s;
while (num > 0) {
s.push_back('0' + num % 10);//取出num的最后一位数字并添加到字符串中
num /= 10; //去掉num的最后一位数字
}
reverse(s.begin(), s.end());//反转字符串以得到正确的数字顺序
return os << s; //输出字符串
}
// 使用 __int128 的动态规划函数
__int128 Do(__int128 N) {
vector<__int128> dp(N + 1, 0);
dp[0] = 1; // 初始化,将0拆分为0个数的方案数为1
for (__int128 i = 1; i <= N; ++i) {
for (__int128 j = i; j <= N; ++j) {
dp[j] += dp[j - i]; // 更新状态
}
}
return dp[N];
}
int main() {
__int128 N;
while(1){
cin >> N;
if(N==0) break;
__int128 result = Do(N);
cout << result << endl;}
return 0;
}