oj.uz

Submission #883846

# Submission time Handle Problem Language Result Execution time Memory
883846 2023-12-06T07:54:17 Z vjudge1 Zapina (COCI20_zapina) C++17
55 / 110
 926 ms 10216 KB 
#include <bits/stdc++.h>
using namespace std;
#define sp << " " << 
#define int long long
#define vi vector<int>
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
#define pii pair<int,int>
const int N = 2e5+1;
const int MOD = 1e9+7;

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));}
int add(int x,int y) {return ((x+y)>=MOD?x+y-MOD:x+y);}
vi fact(N,1);
int nck(int x,int y) {
  if (x < y) return 0;
  if (x < 0) return 0;
  return divide(fact[x],mult(fact[y],fact[x-y])); 
}
void solve() {
  for (int i=2;i<=N;i++) fact[i] = mult(fact[i-1],i); 
  int n;
  cin >> n;
  int lim = (1<<n);
  vi dp(lim);
  for (int mask = 1;mask<lim;mask++) {
    int sm = 0;
    int p = 1,c = 0;
    for (int i=0;i<n;i++) {
      if (mask & (1<<i)) {
        p = mult(p,nck(n-sm,i+1));
        sm+=i+1;
        c++;
      }
    }
    p = mult(p,expo(n-c,n-sm));
    dp[mask] = p;
  }
  int ans = 0;
  for (int i=1;i<lim;i++) {
    int pc = __builtin_popcountll(i);
    if (pc%2) ans = add(ans,dp[i]);
    else ans = add(ans,MOD-dp[i]);
  }
  cout << ans << endl;
}
    
                  
                             
signed main() { 
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  #ifdef Local
  freopen("in","r",stdin);
  freopen("out","w",stdout); 
  #endif
  int t = 1;
  //cin >> t;
	F(i,t) solve();
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1880 KB Output is correct
2 Correct 3 ms 1884 KB Output is correct
3 Correct 3 ms 2032 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct
5 Correct 3 ms 1884 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1880 KB Output is correct
2 Correct 3 ms 1884 KB Output is correct
3 Correct 3 ms 2032 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct
5 Correct 3 ms 1884 KB Output is correct
6 Correct 4 ms 1884 KB Output is correct
7 Correct 4 ms 1884 KB Output is correct
8 Correct 6 ms 1884 KB Output is correct
9 Correct 8 ms 2028 KB Output is correct
10 Correct 15 ms 2168 KB Output is correct
11 Correct 28 ms 2268 KB Output is correct
12 Correct 54 ms 2392 KB Output is correct
13 Correct 108 ms 2908 KB Output is correct
14 Correct 220 ms 3932 KB Output is correct
15 Correct 449 ms 5976 KB Output is correct
16 Correct 926 ms 10216 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1880 KB Output is correct
2 Correct 3 ms 1884 KB Output is correct
3 Correct 3 ms 2032 KB Output is correct
4 Correct 3 ms 1884 KB Output is correct
5 Correct 3 ms 1884 KB Output is correct
6 Correct 4 ms 1884 KB Output is correct
7 Correct 4 ms 1884 KB Output is correct
8 Correct 6 ms 1884 KB Output is correct
9 Correct 8 ms 2028 KB Output is correct
10 Correct 15 ms 2168 KB Output is correct
11 Correct 28 ms 2268 KB Output is correct
12 Correct 54 ms 2392 KB Output is correct
13 Correct 108 ms 2908 KB Output is correct
14 Correct 220 ms 3932 KB Output is correct
15 Correct 449 ms 5976 KB Output is correct
16 Correct 926 ms 10216 KB Output is correct
17 Incorrect 909 ms 4072 KB Output isn't correct
18 Halted 0 ms 0 KB -