Submission #874867

#TimeUsernameProblemLanguageResultExecution timeMemory
874867tsumondaiMagneti (COCI21_magneti)C++14
30 / 110
2538 ms524288 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define fi first #define se second #define pb push_back #define mp make_pair #define foru(i, l, r) for(int i = l; i <= r; i++) #define ford(i, r, l) for(int i = r; i >= l; i--) #define __TIME (1.0 * clock() / CLOCKS_PER_SEC) typedef pair<int, int> ii; typedef pair<ii, int> iii; typedef pair<ii, ii> iiii; const int N = 1e6 + 5; const int oo = 1e9, mod = 1e9 + 7; int n, m, k, r[55], l, pas[1000][100005], x=0, dp[3][55][100005]; int mul(int a, int b) { return (int)a*b%mod; } int add(int a, int b) { return (int)(a+b)%mod; } void pascal() { foru(i,0,l+n) pas[i][0]=1; foru(i,1,l) { foru(j,1,min(n,i)) { pas[i][j]=add(pas[i-1][j], pas[i-1][j-1]); } } return; } void process() { cin >> n >> l; foru(i,1,n) cin >> r[i]; sort(r+1, r+1+n); pascal(); int x=0; dp[0][0][0]=1; foru(i,1,n) { x^=1; dp[x][0][0]=0; int R=r[i]; foru(j,1,i) { foru(k,1,l) { dp[x][j][k]=dp[!x][j-1][k-1]; if (k>=R) dp[x][j][k]=add(dp[x][j][k], mul(dp[!x][j][k-R], 2*j)); if (k>=2*R-1) dp[x][j][k]=add(dp[x][j][k], mul(dp[!x][j+1][k-2*R+1], j*(j+1))); } } } int sol=0; foru(i,1,l) sol=add(sol, mul(dp[x][1][i], pas[l-i+n][n])); cout << sol; return; } signed main() { cin.tie(0)->sync_with_stdio(false); //freopen(".inp", "r", stdin); //freopen(".out", "w", stdout); process(); //cerr << "Time elapsed: " << __TIME << " s.\n"; return 0; } /* Xét các trường hợp đặc biệt Kiểm tra lại input/output Cố gắng trâu Lật ngược bài toán Calm down and get VOI Flow: tìm số cách để sắp xếp n nam châm vào l ô sao cho không có nam châm nào nằm trong đoạn x-r[i]+1, x+r[i]-1 subtask 1: tất cả các nam châm đều bằng nhau phải cách nhau ít nhất n-1 sử dụng công thức tính tổ hợp subtask 2: n<=10 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...