C++ の動作確認をしてみた（５７９）

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題F (Score of Permutations) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 実装に苦労したものの, 何とか分割数の実装(TLE回避版)が出来たので, 良かったと思う.
3. 深さ優先探索(応用版, 分割数) の復習が出来たので, 非常に, 良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 226 解説の各リンクをご覧下さい.

■C++版プログラム(問題F／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc226/editorial/2878
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
const LL MOD = 998244353;
LL FAC[66], INV[66];
set<vi> st[66];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t % MOD;
}

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, 66) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, 66)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 3. 分割数(その１).
    // -> TLE版(N = 30 (5604個) で, 495[ms]かかってしまう).
    /*
    auto f = [&](int cur) -> void {
        st[cur].insert({cur});
        repx(i, 1, cur / 2 + 1){
            set<vi> l = st[i];
            set<vi> r = st[cur - i];
            for(auto &p : l){
                for(auto &q : r){
                    vi v;
                    for(auto &x : p) v.pb(x);
                    for(auto &x : q) v.pb(x);
                    sort(all(v));
                    st[cur].insert(v);
                }
            }
        }
    };
    repx(i, 1, N + 1) f(i);
    */
    /*
    repx(i, 1, 31) f(i);
    printf("%d\n", st[30].size());
    for(auto &p : st[30]){
        for(auto &q : p) printf("%d ", q);
        puts("");
    }
    */
    
    // 4. 分割数(その２).
    // -> TLE回避版(N = 50 (204226個) で, 237[ms]程度).
    set<vi> pf;
    auto dfs = [&](auto &&self, vi vCur, int tCur) -> void {
        // 4-1. 終了条件.
        if(tCur > N) return;
        
        // 4-2. 分割完了.
        if(tCur == N){
            pf.insert(vCur);
            return;
        }
        
        
        // 4-3. すでに分割済みの状態から, 分割を繰り返す.
        int s = 1;
        if(vCur.size()) s = vCur.back();
        repx(i, s, N + 1 - tCur){
            vi vNex = vCur;
            int tNex = tCur;
            vNex.pb(i);
            tNex += i;
            self(self, vNex, tNex);
        }
    };
    dfs(dfs, {}, 0);
    /*
    for(auto &p : pf){
        for(auto &q : p) printf("%d ", q);
        puts("");
    }
    */
    
    // 5. スコアを集計.
    LL ans = 0;
    for(auto &p : pf){
        // 5-1. 巡回置換の分割を一つ取ってくる.
        int c[66];
        rep(i, 66) c[i] = 0;
        for(auto &q : p) c[q]++;
        
        // 5-2. 前項の巡回置換の分割を満たす個数を計算.
        // -> 解説にある数式を適用.
        vi v;
        LL s = FAC[N];
        rep(i, 66){
            if(c[i]){
                s *= mPow(INV[i], c[i]);
                s %= MOD;
                s *= INV[c[i]];
                s %= MOD;
                s *= mPow(FAC[i - 1], c[i]);
                s %= MOD;
                
                // 巡回置換の長さを保存.
                v.pb(i);
            }
        }
        
        // 5-3. スコアを計算.
        // -> MOD版使わずに, とりあえず, 実装.
        LL lcm = 1;
        for(auto &q : v){
            LL g = __gcd(lcm, (LL)q);
            lcm *= q;
            lcm /= g;
        }
        
        // 5-4. スコアを集計.
        ans += mPow(lcm, K) * s;
        ans %= MOD;
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

// 解き直し.

// https://atcoder.jp/contests/abc226/editorial/2878

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

#define all(x) x.begin(), x.end()

const LL MOD = 998244353;

LL FAC[66], INV[66];

set<vi> st[66];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

int main(){

// 1. 入力情報.

int N, K;

scanf("%d %d", &N, &K);

// 2. 事前計算.

FAC[0] = 1;

repx(i, 1, 66) FAC[i] = (LL)i * FAC[i - 1] % MOD;

rep(i, 66) INV[i] = mPow(FAC[i], MOD - 2);

// 3. 分割数(その１).

// -> TLE版(N = 30 (5604個) で, 495[ms]かかってしまう).

auto f = [&](int cur) -> void {

st[cur].insert({cur});

repx(i, 1, cur / 2 + 1){

set<vi> l = st[i];

set<vi> r = st[cur - i];

for(auto &p : l){

for(auto &q : r){

vi v;

for(auto &x : p) v.pb(x);

for(auto &x : q) v.pb(x);

sort(all(v));

st[cur].insert(v);

}

};

repx(i, 1, N + 1) f(i);

repx(i, 1, 31) f(i);

printf("%d\n", st[30].size());

for(auto &p : st[30]){

for(auto &q : p) printf("%d ", q);

puts("");

}

// 4. 分割数(その２).

// -> TLE回避版(N = 50 (204226個) で, 237[ms]程度).

set<vi> pf;

auto dfs = [&](auto &&self, vi vCur, int tCur) -> void {

// 4-1. 終了条件.

if(tCur > N) return;

// 4-2. 分割完了.

if(tCur == N){

pf.insert(vCur);

return;

}

// 4-3. すでに分割済みの状態から, 分割を繰り返す.

int s = 1;

if(vCur.size()) s = vCur.back();

repx(i, s, N + 1 - tCur){

vi vNex = vCur;

int tNex = tCur;

vNex.pb(i);

tNex += i;

self(self, vNex, tNex);

}

};

dfs(dfs, {}, 0);

for(auto &p : pf){

for(auto &q : p) printf("%d ", q);

puts("");

}

// 5. スコアを集計.

LL ans = 0;

for(auto &p : pf){

// 5-1. 巡回置換の分割を一つ取ってくる.

int c[66];

rep(i, 66) c[i] = 0;

for(auto &q : p) c[q]++;

// 5-2. 前項の巡回置換の分割を満たす個数を計算.

// -> 解説にある数式を適用.

vi v;

LL s = FAC[N];

rep(i, 66){

if(c[i]){

s *= mPow(INV[i], c[i]);

s %= MOD;

s *= INV[c[i]];

s %= MOD;

s *= mPow(FAC[i - 1], c[i]);

s %= MOD;

// 巡回置換の長さを保存.

v.pb(i);

}

// 5-3. スコアを計算.

// -> MOD版使わずに, とりあえず, 実装.

LL lcm = 1;

for(auto &q : v){

LL g = __gcd(lcm, (LL)q);

lcm *= q;

lcm /= g;

}

// 5-4. スコアを集計.

ans += mPow(lcm, K) * s;

ans %= MOD;

}

// 6. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
2 2

[出力例]
5
※AtCoderテストケースより

[入力例]
3 3

[出力例]
79
※AtCoderテストケースより

[入力例]
50 10000

[出力例]
77436607
※AtCoderテストケースより

[入力例]
5 1

[出力例]
471

[入力例]
7 3

[出力例]
1922299

[入力例]
20 21

[出力例]
147970674

[入力例]
60 2021

[出力例]
139835665
※ 整数 N が, 問題文の制約条件から範囲外であるケース.

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

[出力例]

※AtCoderテストケースより

[入力例]

50 10000

[出力例]

77436607

※AtCoderテストケースより

[入力例]

5 1

[出力例]

471

[入力例]

7 3

[出力例]

1922299

[入力例]

20 21

[出力例]

147970674

[入力例]

60 2021

[出力例]

139835665

※ 整数 N が, 問題文の制約条件から範囲外であるケース.

■参照サイト
AtCoder Beginner Contest 226

C++の練習を兼ねて, AtCoder Beginner Contest 226 の 問題F (Score of Permutations) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 226 の問題F (Score of Permutations) を解いてみた.

コメントを残すコメントをキャンセル