杭电多校6补题记录

1001: Road To The 3rd Building （HDU 6827）

参考: https://blog.csdn.net/fztsilly/article/details/107847396

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<int, ll>
#define sqr(x) ((x)*(x))
using namespace std;

const ll mod = 1e9 + 7;
const int maxn = 2e5 + 1000;
ll a[maxn], pre[maxn];

ll qpow(ll base, int t){
    ll ret = 1;
    while(t){
        if(t & 1) ret = ret * base % mod;
        t >>= 1;
        base = base * base % mod;
    }
    return ret;
}

void solve(){
    ll n; cin >> n;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        pre[i] = (pre[i-1] + a[i]) % mod;
    }

    ll ans = 0, sum = 0, l = 0, r = n;
    for(int i=1; i<=(n>>1); i++){
        sum = (sum + pre[r] - pre[l] + mod) % mod;
        r--, l++;
        ans = (ans + sum * qpow(i, mod - 2) % mod) % mod;
        ans = (ans + sum * qpow(n - i + 1, mod - 2) % mod) % mod;
    }

    if(n & 1){
        sum = (sum + a[(n >> 1) + 1]) % mod;
        ans = (ans + sum * qpow((n >> 1) + 1, mod - 2) % mod) % mod;
    }

    cout << (ans * qpow((n + 1) * n / 2 % mod, mod - 2) % mod) << '\n';
}

signed main(){
    Android;
    int t; cin >> t;
    while(t--){
        solve();
    }
}

1005: Fragrant numbers (HDU 6831)

参考：https://blog.csdn.net/tianyizhicheng/article/details/107847387

长度不会超过11，仅3,7无法被表示，接着大暴力即可

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define int128 __int128_t
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define redirect_input freopen("./input.txt", "r", stdin);
#define redirect_output freopen("./output.txt", "w", stdout);
#define debug(s, r) std::cerr << #s << ": " << (s) << (r==0?' ':'\n')
#define pii pair<int, ll>
#define sqr(x) ((x)*(x))
using namespace std;

const ll mod = 1e9 + 7;

template<typename F, typename... Args>
void timeit(F func, Args&&... args){
    clock_t start = clock();
    func(std::forward<Args>(args)...);
    # ifndef ONLINE_JUDGE
    cerr << "time: " << ((double)clock() - start) / CLOCKS_PER_SEC << endl;
    # endif
}

const int maxn = 5000 + 10;
const char buffer[] = "11451419191145141919";
bool dp[14][14][maxn + 50] = {0};
int ans[maxn];

void solve(){
    const int maxr = 11;

    for(int len=1; len<=4; len++){
        for(int st=0; st + len - 1 < maxr; st++){
            int v = 0;
            for(int k=0; k<len; k++) v = v * 10 + buffer[st + k] - '0';
            if(v < maxn) dp[st][st + len - 1][v] = true;
        }
    }

    for(int len=2; len<=maxr; len++){
        for(int st=0, ed; st + len - 1 < maxr; st++){
            ed = st + len - 1;
            for(int mid = st; mid < ed; mid++){
                for(int i=1; i<maxn; i++){
                    if(!dp[st][mid][i]) continue;
                    for(int j=1; j<maxn; j++){
                        if(!dp[mid + 1][ed][j]) continue;
                        if(i + j < maxn) dp[st][ed][i + j] = true;
                        if(i * j < maxn) dp[st][ed][i * j] = true;
                    }
                }
            }
            
        }
    }

    memset(ans, -1, sizeof ans);
    for(int i=0; i<maxr; i++){
        for(int j=1; j<maxn; j++){
            if(dp[0][i][j] && ans[j] == -1) {
                ans[j] = i + 1;
            }
        }
    }

    // int mx = 0, neg_cnt = 0; 
    // for(int i=1; i<maxn; i++){
    //     mx = max(mx, ans[i]);
    //     if(ans[i] == -1) {
    //         neg_cnt++;
    //         // cerr << i << " ";
    //     }
    // }
    // cerr << endl;
    // debug(mx, 0), debug(neg_cnt, 1); // 调整maxr,使得neg_cnt=2
}

signed main(){
    Android;
    timeit(solve);
    int t, n; cin >> t;
    while(t--){
        cin >> n;
        cout << ans[n] << '\n';
    }
}

1010: Expectation (HDU 6836)

矩阵树

1007: A Very Easy Math Problem