結果

問題 No.1043 直列大学
ユーザー tamarontamaron
提出日時 2020-05-01 22:56:37
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,768 bytes
コンパイル時間 1,759 ms
コンパイル使用メモリ 176,764 KB
実行使用メモリ 19,152 KB
最終ジャッジ日時 2024-06-07 11:17:48
合計ジャッジ時間 3,267 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
18,944 KB
testcase_01 AC 18 ms
18,816 KB
testcase_02 AC 20 ms
18,816 KB
testcase_03 AC 18 ms
18,944 KB
testcase_04 AC 18 ms
18,816 KB
testcase_05 AC 20 ms
18,816 KB
testcase_06 AC 19 ms
18,816 KB
testcase_07 AC 18 ms
18,864 KB
testcase_08 AC 19 ms
18,944 KB
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 20 ms
18,944 KB
testcase_15 AC 19 ms
18,844 KB
testcase_16 AC 20 ms
18,944 KB
testcase_17 AC 19 ms
18,816 KB
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 AC 19 ms
18,944 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void yn(bool j){cout << (j ? "Yes" : "No") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> long long bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

// typedef long long mint;
struct mint {
long long x;
    mint(long long x = 0):x((x % MOD + MOD) % MOD){}
    mint& operator += (const mint a) {if ((x += a.x) >= MOD) x -= MOD; return *this;}
    mint& operator -= (const mint a) {if ((x += MOD-a.x) >= MOD) x -= MOD; return *this;}
    mint& operator *= (const mint a) {(x *= a.x) %= MOD; return *this;}
    mint operator + (const mint a) const {mint res(*this); return res += a;}
    mint operator - (const mint a) const {mint res(*this); return res -= a;}
    mint operator * (const mint a) const {mint res(*this); return res *= a;}
    mint pow(long long t) const {if (!t) return 1; mint a = pow(t >> 1); a *= a; if (t&1) a *= *this; return a;}
    mint inv() const {return pow(MOD - 2);}
    mint& operator /= (const mint a) {return (*this) *= a.inv();}
    mint operator / (const mint a) const {mint res(*this); return res /= a;}
};

class combination {
    public:
    vector<mint> fact, ifact;
    combination(int n):fact(n + 1), ifact(n + 1) {
        assert(n < MOD);
        fact[0] = 1;
        for(int i = 1; i <= n; ++i) fact[i] = fact[i - 1] * i;
        ifact[n] = fact[n].inv();
        for(int i = n; i >= 1; --i) ifact[i - 1] = ifact[i] * i;
    }
    mint operator()(int n, int k) {
        if (k < 0 || k > n) return 0;
        if (COMBMAX < n){
            mint ret = 1;
            for(long long i = 1; i <= k; i++){
                ret *= (n - i + 1);
                ret /= i;
            }
            return ret;
        }
        return fact[n] * ifact[k] * ifact[n - k];
    }

    mint multi(long long n, long long sum, long long l, long long r){
        long long m = r - l + 1;
        long long t = sum - n * (l - 1);
        mint ans = 0;
        for(long long k = 0; k <= (t - n) / m; k++){
            long long sign = k % 2 == 0 ? 1 : -1;
            mint temp = this->operator() (n, k);
            temp *= this->operator() (n + (t - n - m * k - 1), t - n - m * k);
            temp *= sign;
            ans += temp;
        }
        return ans;
    }
} com(COMBMAX);


int main(){
    ll N, M; cin >> N >> M;
    vector<ll> V(N), R(M);
    rep(i, N) cin >> V[i];
    rep(i, M) cin >> R[i];
    ll A, B; cin >> A >> B;
    ll V_MAX = (N + 2) * 10;
    ll R_MAX = (M + 2) * 10;
    vector<mint> dp_V(V_MAX, 0);
    vector<mint> dp_R(R_MAX, 0);
    dp_V[0] = 1;
    rep(i, N){
        vector<mint> dp_V_next(V_MAX, 0);
        rep(j, V_MAX){
            dp_V_next[j] += dp_V[j];
            if (j + V[i] < V_MAX) dp_V_next[j + V[i]] += dp_V[j];
        }
        dp_V = dp_V_next;
    }

    dp_R[0] = 1;
    rep(i, M){
        vector<mint> dp_R_next(R_MAX, 0);
        rep(j, R_MAX){
            dp_R_next[j] += dp_R[j];
            if (j + R[i] < R_MAX) dp_R_next[j + R[i]] += dp_R[j];
        }
        dp_R = dp_R_next;
    }
    dp_V[0] = 0;
    rep(i, V_MAX - 1) dp_V[i + 1] += dp_V[i];
    // debug(dp_V);
    // debug(dp_R);
    // rep(i, R_MAX - 1) dp_R[i + 1] += dp_R[i];
    mint ans = 0;
    // pt(A, B);
    for(ll res = 1; res < R_MAX; res++){
        mint temp = dp_V[min(res * B, V_MAX - 1)];
        temp -= dp_V[min(res * A - 1, V_MAX - 1)];
        temp *= dp_R[res];
        // pt(temp);
        ans += temp;
    }
    pt(ans.x);

}
0