제출 #1126983

#제출 시각아이디문제언어결과실행 시간메모리
1126983seoul_koreaZapina (COCI20_zapina)C++20
22 / 110
20 ms328 KiB
/** faksld fjkladsj kfolsdajk l fjkdlas jflksadklj fjklsd **/ #include <bits/stdc++.h> using namespace std; #define int long long #define REP(i, n) for(int i = 1; i <= n; i++) #define FOR(i, a, b) for(auto i = a; i <= b; i++) #define FORD(i, a, b) for(auto i = a; i >= b; i--) template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; } template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; } mt19937 rng(time(0)); const int N = 1000, MOD = (int)1e9 + 7; void add(int& a, int b) { a += b; if(a < 0) a += MOD; a %= MOD; } int n; namespace Subtask1 { int gr[N], ans = 0; void Backtrack(int p) { if(p == n + 1) { vector<int> c(n + 1); REP(i, n) c[gr[i]]++; bool ok = 0; REP(i, n) if(c[i] == i) ok = 1; ans += ok; return; } REP(i, n) { gr[p] = i; Backtrack(p + 1); } } void Solve() { Backtrack(1); cout << ans; } } int POW(int a, int b) { int res = 1; for(; b; b >>= 1, a = 1ll * a * a % MOD) if(b & 1) res = 1ll * res * a % MOD; return res; } int dp[N][N], C[N][N]; signed main(void) { cin.tie(nullptr)->sync_with_stdio(false); #define TASK "" if(fopen(TASK".INP", "r")) { freopen(TASK".INP", "r", stdin); freopen(TASK".OUT", "w", stdout); } cin >> n; if(n <= 7) return Subtask1::Solve(), 0; else { FOR(i, 0, n) { C[i][0] = 1; REP(j, i) { C[i][j] = C[i - 1][j]; add(C[i][j], C[i - 1][j - 1]); } } int tot = POW(n, n); dp[0][0] = 1; FOR(i, 0, n - 1) { FOR(j, 0, n) { FOR(k, 0, n - j) { if(k != i + 1) { add(dp[i + 1][j + k], 1ll * dp[i][j] * C[n - j][k] % MOD); } } } } cout << (tot - dp[n][n]) % MOD; } return 0; }

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

zapina.cpp: In function 'int main()':
zapina.cpp:71:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
zapina.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...