2020杭電多校5(補)

1001 Tetrahedron
に言及
1つの直角四面体の3つの直角辺は([1,n])の範囲内でランダムで、直角頂点から対面までの距離の二乗逆数((frac{1}{h^2}))の期待値を求める.
構想
まずベクトル計算により(frac{1}{h^2}=frac{1}{a^2}+frac{1}{b^2}+frac{1}{c^2})が得られ,そこで(E(frac{1}{h^2})=3 E(frac{1}{a^2})quad,そのうちain[1,n])が発売される.
\[answer=\frac{3}{n}\sum_{i=1}^{n}\frac{1}{i^2}\(mod\quad 998244353)\]
逆元の前処理方法に注意してください.(inv[i]=mod-mod/i*inv[mod%i]).
コード#コード#

#include 
#define ll long long
using namespace std;
const int maxn = 6e6 + 7;
const int mod = 998244353;

int T, n;
int ni[maxn], sum[maxn];
void init() {
    ni[1] = sum[1] = 1;
    for(int i = 2; i < maxn; i++) {
        ni[i] = mod - 1LL * mod/i * ni[mod%i] % mod;
        sum[i] = sum[i-1] + 1LL * ni[i] * ni[i] % mod;
        sum[i] %= mod;
    }
}
ll qpow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    init();
    cin >> T;
    while(T--) {
        cin >> n;
        cout << 1LL * sum[n] * 3 % mod * qpow(n, mod - 2) % mod << endl;
    }
    return 0;
}

1003 Boring Game
に言及
テーブルの上にn枚の紙を重ねて、これらの紙を左から右にk回折り畳んで、全部で階層化します(2*n*(1<層、これらの層に対して1から番号をつけて、1組の折り畳み後の番号をあげて、折り畳む前にこれらの番号が上から下まで、左から右のシーケンスを聞きます.
構想
配列でシミュレーションし、折りたたむたびに折りたたまれた中点を見つけ、中点の上の逆順を下の配列に加えます.
コード#コード#

#include 
#define ll long long
using namespace std;
const int maxn = 5e5 + 7;
const int mod = 1e9 + 7;

int T, n, k;
vector v[maxn];
void slove(int l, int r) {
    int mid = (l + r) / 2, now = mid + 1;
    for(int i = mid; i >= l; i--) {
        for(int j = v[i].size() - 1; j >= 0; j--) {
            v[now].push_back(v[i][j]);
        }
        now++;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    cin >> T;
    while(T--) {
        cin >> n >> k;
        int len = 2 * n * (1 << k);
        for(int i = 0; i < maxn; i++) v[i].clear();
        for(int i = 0; i < len; i++) {
            int temp; cin >> temp;
            v[i].push_back(temp);
        }
        int l = 0, r = len - 1;
        for(int _ = 0; _ < k; _++) {
            slove(l, r);
            l += (r - l) / 2 + 1;
        }
        for(int i = l; i <= r; i++) {
            reverse(v[i].begin(), v[i].end());
            for(int j = 0; j < v[i].size(); j++) {
                cout << v[i][j];
                if(i == r && j == v[i].size() - 1) cout << endl;
                else cout << ' ';
            }
        }
    }
    return 0;
}

1009 Paperfolding
に言及
1枚の紙に、水平に折り、縦に折り、全部でn回((2^n)の折り方があることを意味する)行い、最後に紙を十字に切り、多くのブロックに分け、ブロック数の数学的期待を求める.
構想
水平にx回折り、縦にy回折り、折りたたんだ紙を広げてみると、切り裂いた跡は原紙を縦方向に(2^x)ナイフ、水平方向に(2^y)ナイフを切ったので、全部で((2^x+1)*(2^y+1))ブロックが切り裂かれています.
だから望むのは
\[\begin{align} ans &=\frac{1}{2^n}\\sum_{i=0}^{n}\C_n^i\(2^i+1)*(2^{n-i}+1)\\&=\frac{1}{2^n}\\sum_{i=0}^{n}\C_n^i\(2^n+2^i+2^{n-i}+1)\\&= 2^n+1+2*\frac{1}{2^n}\sum_{i=0}^{n}\C_n^i 2^i\\&= 2^n+1+2*\frac{3^n}{2^n}\end{align}\]
コード#コード#

#include 
#define ll long long
using namespace std;
const int maxn = 1e5 + 7;
const int mod = 998244353;

ll T, n;
ll qpow(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    ll inv2 = qpow(2, mod - 2);
    cin >> T;
    while(T--) {
        cin >> n;
        ll ans = 1 + qpow(2, n % (mod - 1)) + 2 * qpow(3 * inv2, n % (mod - 1));
        ans %= mod;
        cout << ans << endl;
    }
    return 0;
}

1012 Set1
に言及
1つの初期要素が({1,...,n})の集合は、1つの要素しか残っていないまで2つの操作を順次行います.

コレクションの最小要素

を除去する.

ランダムに要素を除去する

数字ごとに残された期待値を聞く
構想
(i)番目の要素については、左の要素の数が右の要素の数より少なくなく、右の要素の数が2番目の操作で除去されることが残りの条件です.
そこで、それぞれの数について残されたシナリオ数は(cnt[i]=C_{r}^{l}r!\frac{( r-l)!}{(2!)^{(r-l)/2}\frac{r-l}{2}})のうち、(l)は(i)の左の数の個数であり、(r)は(i)の右の数の個数である.
答えは,各シナリオ数(cnt[i])をシナリオ数を除いて加算(sum)である.
コード#コード#

#include 
#define ll long long
using namespace std;
const int maxn = 5e6 + 7;
const int mod = 998244353;

int T, n;
int cnt[maxn], fac[maxn], inv[maxn], sum;

int qpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = (ll)ans * a % mod;
        a = (ll)a * a % mod;
        b >>= 1;
    }
    return ans;
}

void init() {
    fac[0] = inv[0] = 1;
    for(int i = 1; i < maxn; i++) fac[i] = (ll)fac[i - 1] * i % mod;
    inv[maxn - 1] = qpow(fac[maxn - 1], mod - 2);
    for(int i = maxn - 2; i >= 1; i--) inv[i] = (ll)inv[i + 1] * (i + 1) % mod;
}

ll C(ll n, ll m) {
    return (ll)fac[n] * inv[m] % mod * inv[n - m] % mod;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    freopen("data.in", "r", stdin);
    //freopen("data.out", "w", stdout);
    init();
    cin >> T;
    while(T--) {
        sum = 0;
        cin >> n;
        for(int i = 1; i <= n; i++) {
            int l = i-1, r = n-i;
            if(l >= r) {
                int res = (ll)C(l, r) * fac[r] % mod;
                int temp = qpow(2, (l-r)/2);
                temp = qpow(temp, mod - 2);
                res = (ll)res * fac[l-r] % mod * temp % mod;
                res = (ll)res * inv[(l-r)/2] % mod;
                cnt[i] = res;
                sum = ((ll)sum + cnt[i]) % mod;
            }
            else cnt[i] = 0;
        }
        sum = qpow(sum, mod - 2);
        for(int i = 1; i <= n; i++) {
            cout << (ll)cnt[i] * sum % mod;
            if(i != n) cout << ' ';
        }
        cout << endl;
    }
    return 0;
}