Submission #19868

#	Time	Username	Problem	Language	Result	Execution time	Memory
19868		yongwhan	괄호 (kriii4_R)	C++14	100 / 100	912 ms	17336 KiB

R

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
const int mx=1e6+5;
typedef long long ll;

ll fact[mx], f[mx];

ll exp(ll a, ll b, ll m) {
  ll r=1;
  while(b) {
    if(b%2) r=(r*a)%m;
    a=(a*a)%m;
    b/=2;
  }
  return r;
}

ll inv(ll a, ll m) {
  return exp(a,m-2,m);
}

int binom(int n, int m, int mod) {
  ll a=fact[n], b=fact[m], c=fact[n-m];
  ll ret=a*inv(b,mod);
  ret%=mod;
  ret*=inv(c,mod);
  ret%=mod;
  return ret;
}

ll catalan(int n, int mod) {
  ll a=fact[2*n], b=fact[n+1], c=fact[n];
  ll ret=a*inv(b,mod);
  ret%=mod;
  ret*=inv(c,mod);
  ret%=mod;
  return ret;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  fact[0]=1;
  for (int i=1; i<mx; i++)
    fact[i]=(fact[i-1]*i)%mod;

  ll n,k; cin>>n>>k;
  f[0]=1;
  for (int i=1; i<=n; i++) {
    if(i%2==0) f[i]=f[i-1]*(k+1)%mod;
    else {
      f[i]=(f[i-1]*(k+1))%mod;
      ll add=(exp(k,i/2,mod)*catalan(i/2,mod))%mod;
      f[i]=(f[i]+(mod-add))%mod;
    }
  }
  cout << f[n] << endl;
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92