HDU 5047 Sawtooth 规律+ C++大数模拟 2014 ACM/ICPC Asia Regional Shanghai Online
来源：程序员人生 发布时间：2014-10-05 02:56:47 阅读次数：2191次
题意：
用x个大M 可以把平面分成至多几块。
就是折线切割平面的加强版。
一个简单的递推式 : F(x+1) = 16x+1+F(x)
然后转成通项公式，然后C++ 位压大数模拟
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 100000;
struct node {
int v[10];
node() {
memset(v, 0, sizeof v);
v[0] = 1;
}
void out() {
printf("%d", v[v[0]]);
for (int i = v[0] - 1; i >= 1; --i)
printf("%05d", v[i]);
putchar('
');
}
};
char ch;
void get(ll& x) {
while ((ch = getchar()) < '0' || ch > '9');
x = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9')
x = x * 10 + ch - '0';
}
void add(node& i, ll x) {
int mx = 0;
while (x > 0) {
++ mx;
x = x + i.v[mx];
i.v[mx] = x % mod;
x /= mod;
}
if (mx > i.v[0])
i.v[0] = mx;
}
void multi(node& a, ll x) {
ll y = 0;
for (int i = 1; i <= a.v[0]; ++i) {
y = a.v[i] * x + y;
a.v[i] = y % mod;
y /= mod;
}
int mx = a.v[0];
while (y > 0) {
++ mx;
a.v[mx] = y % mod;
y /= mod;
}
a.v[0] = mx;
}
node Cal(ll n) {
node re;
if (n == 1) {
re.v[1] = 2;
} else {
add(re, n * 8);
multi(re, n - 1);
add(re, n + 1);
}
return re;
}
int main() {
node one;
one.v[1] = 1;
int T = 0, cas;
ll n;
node ans;
scanf("%d", &cas);
while (cas -- > 0) {
get(n);
ans = Cal(n);
printf("Case #%d: ", ++T);
ans.out();
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
