D - Modulo Operations

https://atcoder.jp/contests/exawizards2019/tasks/exawizards2019_d

解法

sをソートして、s[i]を最初に使った場合の合計を考えていく。

ここでx%s[i] はs[i] より小さくなるため、今後s[i]より右でmodを取っても答えは変わらない。

よってこの答えは

s[0~i)で(x%s[i])から作れる数の合計 * 右の並び替え方 * 左右の入れ替え方 となり

rec(n,x) := [0 n)でxから作れる数の合計として

rec( i, x%s[i]) * (n-i-1)! * (n-1)C(n-i-1) となる　

メモ化だが間に合わないので、部分問題ごとに枝狩りする

枝狩り１　

a[0] > x の時 return n! * x;

枝狩り 2   

s[i]がxより大きいとき  s[i]を初めに使った時の合計とs[i+1] ~ s[n-1] を初めに使った時の合計は等しくなるため計算しなくていい

なぜならxに影響のある数と無い数の状況が同じだから

以上をやったら通った

https://atcoder.jp/contests/exawizards2019/submissions/4879849

const int NUM_ = 1400001;
static ll fac[NUM_ + 1], finv[NUM_ + 1], inv[NUM_ + 1];
mint com(int n, int r) {
    if (fac[0] == 0) {
        inv[1] = fac[0] = finv[0] = 1;
        for (int i = 2; i <= NUM_; ++i) inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
        for (int i = 1; i <= NUM_; ++i) fac[i] = fac[i - 1] * i % MOD, finv[i] = finv[i - 1] * inv[i] % MOD;
    }
    if (r < 0 || r > n) return 0;
    return mint(finv[r] * fac[n] % MOD * finv[n - r]);
}
mint ncr(int n, int r) { return com(n, r); }

mint dp[202][k5];
map<int, int> was[202];
mint rec(int n, int x) {
    if (n == 0) {
        return x;
    }
    // n)でxから作れる数
    if (was[n][x])return dp[n][x];
    was[n][x] = 1;

    if (a[0] > x) {
        dp[n][x] += fac[n] * x;
        return dp[n][x];
    }

    //iをまず使う
    rep(i, n) {
        //超えたら以降答え同じ
        if (a[i] > x) {
            int nx = x % a[i];
            mint v = rec(i, nx) * fac[n - i - 1] * ncr(n - 1, n - i - 1);
            dp[n][x] += v * (n - i);//自分も
            break;
        } else {
            int nx = x % a[i];
            dp[n][x] += rec(i, nx) * fac[n - i - 1] * ncr(n - 1, n - i - 1);
        }
    }
    return dp[n][x];
}

void solve() {
    com(1, 1);
    cin >> n >> x;
    a.resize(n);
    cin >> a;
    sort(a);
    cout << rec(n, x) << endl;

}