Submission #883846

#	Time	Username	Problem	Language	Result	Execution time	Memory
883846		vjudge1	Zapina (COCI20_zapina)	C++17	55 / 110	926 ms	10216 KiB

zapina

#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 / 22
• Subtask 2: 33 / 33
• Subtask 3: 0 / 55