제출 #1278645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278645		vuquangsang	Magneti (COCI21_magneti)	C++20	110 / 110	95 ms	58120 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define     FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define     FORD(i, a, b) for(int i = (a); i >= (b); i--)
#define     el "\n"
const int N = 2e4 + 2;
const int sm = 1e9 + 7;

int n, L, r[N];
int dp[55][55][N];

void add(int &x, int y)
{
    x += y;
    if(x >= sm) x -= sm;
}

int fac[N], inv_fac[N];

int Pow(int a, int n)
{
    if(!n) return 1;
    int res = Pow(a, n / 2);
    res = 1LL * res * res % sm;
    if(n & 1) res = 1LL * res * a % sm;
    return res;
}
void prepare()
{
    fac[0] = inv_fac[0] = 1;
    for(int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % sm;
    inv_fac[N - 1] = Pow(fac[N - 1], sm - 2);
    FORD(i, N - 2, 1) inv_fac[i] = 1LL * inv_fac[i + 1] * (i + 1) % sm;
}
int C(int k, int n)
{
    if(k > n || k < 0) return 0;
    return 1LL * fac[n] * inv_fac[k] % sm * inv_fac[n - k] % sm;
}
int mul(int x, int y)
{
    return 1LL * x * y % sm;
}
void solve()
{
    cin >> n >> L;
    for(int i = 1; i <= n; i++) cin >> r[i];

    sort(r + 1, r + n + 1);


//    dp[0][0][0] = 1;
//    FOR(i, 1, n) FOR(j, 1, i) FOR(d, 1, L){
//        add(dp[i][j][d], dp[i - 1][j - 1][d - 1]);
//        int R = r[i];
//        if(d >= R) add(dp[i][j][d], dp[i - 1][j][d - R] * 2 % sm * j % sm);
//        if(d >= 2 * R - 1) add(dp[i][j][d], dp[i - 1][j + 1][d - 2 * R + 1] * j % sm * (j + 1) % sm);
//    }

    dp[0][0][0] = 1;
    for(int i = 0; i < n; i++) for(int j = 0; j <= i; j++) {
        for(int d = 0; d <= L; d++) {
            add(dp[i + 1][j + 1][d + 1], mul(j + 1, dp[i][j][d]));
            if(d + r[i + 1] <= L) add(dp[i + 1][j][d + r[i + 1]], mul(2 * j, dp[i][j][d]));
            if(j > 0 && d + 2 * r[i + 1] - 1 <= L) add(dp[i + 1][j - 1][d + 2 * r[i + 1] - 1], mul(j - 1, dp[i][j][d]));
        }
    }
    prepare();
    int ans = 0;
    FOR(d, 1, L) {
        // x1 + x2 + .. + xn = L - d
        // x1 >= 0
        // chia L - d o trong cho n + 1 nguoi
        //=> C(n, L - D + n)
        add(ans, 1LL * dp[n][1][d] * C(n, n + L - d) % sm);
    }
    cout << ans;
}

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    #define TASK "magneti"
    if(fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    solve();

    cerr << "\nTime" << 0.001 * clock() << "s "; return 0;


}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp:81:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   81 | main()
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50