結果

問題 No.1634 Sorting Integers (Multiple of K) Hard
ユーザー mugen_1337mugen_1337
提出日時 2021-07-08 14:58:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,390 ms / 3,000 ms
コード長 2,697 bytes
コンパイル時間 2,683 ms
コンパイル使用メモリ 221,740 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 21:48:25
合計ジャッジ時間 31,495 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 6 ms
5,376 KB
testcase_04 AC 5 ms
5,376 KB
testcase_05 AC 977 ms
5,376 KB
testcase_06 AC 988 ms
5,376 KB
testcase_07 AC 987 ms
5,376 KB
testcase_08 AC 918 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 1,365 ms
5,376 KB
testcase_12 AC 1,302 ms
5,376 KB
testcase_13 AC 1,387 ms
5,376 KB
testcase_14 AC 1,390 ms
5,376 KB
testcase_15 AC 1,373 ms
5,376 KB
testcase_16 AC 1,387 ms
5,376 KB
testcase_17 AC 499 ms
5,376 KB
testcase_18 AC 558 ms
5,376 KB
testcase_19 AC 803 ms
5,376 KB
testcase_20 AC 359 ms
5,376 KB
testcase_21 AC 109 ms
5,376 KB
testcase_22 AC 1,085 ms
5,376 KB
testcase_23 AC 1,170 ms
5,376 KB
testcase_24 AC 1,311 ms
5,376 KB
testcase_25 AC 1,350 ms
5,376 KB
testcase_26 AC 1,361 ms
5,376 KB
testcase_27 AC 1,376 ms
5,376 KB
testcase_28 AC 1,378 ms
5,376 KB
testcase_29 AC 1,378 ms
5,376 KB
testcase_30 AC 1,374 ms
5,376 KB
testcase_31 AC 1,385 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
using ll=long long;

// [0, 2^n)のうち，k本bitが立っているものを全列挙
vector<int> enumerate_combination(int n, int k){
    int comb = (1<<k) - 1;
    vector<int> ret;
    while(comb < (1<<n)){
        ret.push_back(comb);
        int x = comb & (-comb),y = comb + x;
        comb = ((comb&~y) / x>>1) | y;
    }
    return ret;
}


signed main(){
    // 階乗をすぐとれるように
    vector<ll> fac(17, 1);
    for(int i = 2; i < 17; i++) fac[i] = fac[i - 1] * i;

    int N; ll K;
    cin >> N >> K;
    vector<int> C(10, 0), A;// Cは数をカウント
    for(int i = 1; i < 10; i++){
        cin >> C[i];
        for(int j = 0; j < C[i]; j++) A.push_back(i);
    }
    
    if(N == 1){
        cout << (A[0] % K == 0) << endl;
        return 0;
    }


    int n = N / 2;
    int m = N - n;

    // 全列挙用の順列を置いておく
    vector<int> ord(n), ord2(m);
    iota(begin(ord), end(ord), 0);
    iota(begin(ord2), end(ord2), 0);

    // 上位桁に掛け合わせる数を求めておく
    ll offset = 1;
    rep(i,m) offset *= 10;
    offset %= K;

    unordered_map<ll, ll> memo;

    ll res = 0;
    for(auto state : enumerate_combination(N, n)){
        vector<int> v, w;
        ll vnum = 0;
        rep(i, N){
            if((state>>i) & 1){
                v.push_back(A[i]);
                vnum = vnum * 10 + A[i];
            }
            else w.push_back(A[i]);
        }

        // もうすでに求めたことがあるものは省略
        // これでかなり枝刈りになるのでここがないと死ぬ
        if(memo.count(vnum)){
            res += memo[vnum];
            continue;
        }
        
        unordered_map<ll, ll> mp;
        
        sort(begin(ord), end(ord));
        sort(begin(ord2), end(ord2));

        // 上位桁を全列挙
        do{
            ll S = 0;
            for(auto &i : ord) S = (S * 10 + v[i]) % K;
            S = (S * offset) % K;// 上位桁なので10^mを掛け合わせる
            mp[S]++;
        }while(next_permutation(begin(ord), end(ord)));

        // 下位桁を全列挙
        ll add = 0;   
        do{
            ll S = 0;
            for(auto &i : ord2) S = (S * 10 + w[i]) % K;
            add += mp[(K-S) % K];
        }while(next_permutation(begin(ord2), end(ord2)));
        res += add;
        memo[vnum] = add;// 次のためにメモを残す
    }

    // 被りを除く
    for(int i = 1; i < 10 ; i++) res /= fac[C[i]];

    cout << res << endl;
    return 0;
}
0