HDU 5047 Sawtooth法則+C++大数シミュレーション2014 ACM/IPCC Asia Regional Shanghai Online

タイトル:
x個の大きいMで平面を複数のブロックに分けることができる.
折れ線カット平面の補強版です.
簡単な繰返し:F(x+1)=16 x+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;
}