結果

問題 No.1634 Sorting Integers (Multiple of K) Hard
ユーザー mugen_1337
提出日時 2021-07-08 14:58:45
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,384 ms / 3,000 ms
コード長 2,697 bytes
コンパイル時間 7,952 ms
コンパイル使用メモリ 283,232 KB
最終ジャッジ日時 2025-01-22 18:10:42
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

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