Lucky Pascal Triangle(Gym - 102091F + 打表)

#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;

#define lson (rt<<1)
#define rson (rt<<1|1)
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********\n")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("/home/dillonh/CLionProjects/Dillonh/in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)

const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 200000 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;

inline LL read() {
    int f = 0;
    LL x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x = f ? -x : x;
}

int add(int x, int y) {
    x = x + y;
    if(x >= mod) x -= mod;
    if(x < 0) x += mod;
    return x;
}

unordered_map<LL,int> num;

int dfs(LL n, LL nw) {
    if(nw == 1) return 0;
    int row = n / nw % mod;
    int ans = 0, tmp = 0;
    if(row & 1) {
        if(row >= 1) tmp = 1LL * (row - 1) / 2 % mod * (row % mod) % mod;
        ans = 1LL * (row + 1) / 2 % mod * (row % mod) % mod * num[nw] % mod;
    } else {
        if(row >= 1) tmp = 1LL * row / 2 % mod * ((row - 1) % mod) % mod;
        ans = 1LL * row / 2 % mod * ((row + 1) % mod) % mod * num[nw] % mod;
    }
    tmp = 1LL * tmp * ((nw - 1) / 2 % mod) % mod * (nw % mod) % mod;
    ans = add(ans, tmp);
    n %= nw;
    if(n == 0) return ans;
    ans = add(ans, 1LL * add(row, 1) * dfs(n, nw / 7) % mod);
    if(n & 1) {
        ans = add(ans, 1LL * row * ((nw - 1 + nw - n) / 2 % mod) % mod * (n % mod) % mod);
    } else {
        ans = add(ans, 1LL * row * (n / 2 % mod) % mod * ((nw - 1 + nw - n) % mod) % mod);
    }
    return ans;
}

LL pw[25];

int main() {
#ifndef ONLINE_JUDGE
    FIN;
    time_t st = clock();
#endif
    int _;
    scanf("%d", &_);
    pw[0] = 1;
    for(int i = 1; i <= 21; ++i) pw[i] = pw[i-1] * 7, num[pw[i]] = dfs(pw[i], pw[i-1]);
    for(int __ = 1; __ <= _; ++__) {
        LL n;
        n = read();
        ++n;
        LL nw = lower_bound(pw + 1, pw + 22, n) - pw;
        if(pw[nw] != n) nw = pw[nw-1];
        else nw = pw[nw];
//        dfs(n, nw);
        printf("Case %d:%d\n", __, dfs(n, nw));
    }
#ifndef ONLINE_JUDGE
    printf("It costs %.3fs\n", 1.0 * (clock() - st) / CLOCKS_PER_SEC);
#endif
    return 0;
}