제출 #1080304

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1080304		dosts	Magneti (COCI21_magneti)	C++17	0 / 110	47 ms	2008 KiB

Main

//Dost SEFEROĞLU
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>
const int MOD = 1e9+7,inf = 2e18;
const int N = 1e6+50;
 
int add(int x,int y) {
    return ((x+y) >= MOD ? x+y-MOD : x+y);
}
int mult(int x,int y) {
    return ((x%MOD)*(y%MOD))%MOD;
}
int expo(int x,int y) {
    if (!y) return 1;
    int e = expo(x,y/2);
    e = mult(e,e);
    if (y&1) e = mult(e,x);
    return e;
}
int divide(int x,int y) {
    return mult(x,expo(y,MOD-2));
}
vi f(100001,1),finv(100001);
int nck(int n,int k) {
    if (n < k) return 0;
    return mult(f[n],mult(finv[n-k],finv[k]));
}

int puzzle(int n,int bosluk) {
    return nck(n+bosluk,n);
}
void solve() {
    for (int i=1;i<=100000;i++) f[i] = mult(f[i-1],i);
    for (int i=0;i<=100000;i++) finv[i] = divide(1,f[i]);
    int n,l;
    cin >> n >> l;
    if (n == 1) {
        cout << l << endl;
        return;
    }
    int s = 0;
    vi a(n+1);
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        s+=2*a[i]-1;
    }
    int ans = 0;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            if (i == j) continue;
            for (int L = a[i];L<=2*a[i]-2;L++) {
                for (int R = a[j];R<=2*a[j]-2;R++) {
                    int leftover = l-L-R-(s-2*a[i]-2*a[j]+2);
                    int contrib = mult(f[n-2],puzzle(n-2,leftover));
                    ans = add(ans,contrib);
                }
            }
        }
    }
    for (int i=1;i<=n;i++) {
        for (int L=a[i];L<=2*a[i]-2;L++) {
            int leftover = l-L-(s-2*a[i]+1);
            ans = add(ans,mult(2,mult(f[n-1],puzzle(n-1,leftover))));
        }
    }
    if (s <= l) ans = add(ans,mult(f[n],puzzle(n,l-s)));
    cout << ans << endl;
}                    
                             
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

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