結果

問題 No.391 CODING WAR
ユーザー __NCAstar__NCAstar
提出日時 2020-06-28 22:05:51
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 916 ms / 2,000 ms
コード長 2,905 bytes
コンパイル時間 1,068 ms
コンパイル使用メモリ 160,672 KB
実行使用メモリ 9,732 KB
最終ジャッジ日時 2024-07-08 08:22:37
合計ジャッジ時間 9,290 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 123 ms
9,640 KB
testcase_01 AC 121 ms
9,708 KB
testcase_02 AC 126 ms
9,584 KB
testcase_03 AC 120 ms
9,556 KB
testcase_04 AC 118 ms
9,592 KB
testcase_05 AC 119 ms
9,528 KB
testcase_06 AC 120 ms
9,668 KB
testcase_07 AC 120 ms
9,720 KB
testcase_08 AC 118 ms
9,572 KB
testcase_09 AC 916 ms
9,552 KB
testcase_10 AC 741 ms
9,576 KB
testcase_11 AC 121 ms
9,692 KB
testcase_12 AC 119 ms
9,588 KB
testcase_13 AC 806 ms
9,524 KB
testcase_14 AC 750 ms
9,584 KB
testcase_15 AC 841 ms
9,404 KB
testcase_16 AC 551 ms
9,732 KB
testcase_17 AC 603 ms
9,452 KB
testcase_18 AC 458 ms
9,700 KB
testcase_19 AC 477 ms
9,716 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define pb push_back
#define fst first
#define snd second

using namespace std;

typedef long long ll;
typedef pair<int,int> ii;

inline bool LT(double a,double b) { return !equals(a,b) && a < b; }
inline bool LTE(double a,double b) { return equals(a,b) || a < b; }

const ll mod = 1000000007LL;

long long extgcd(long long a,long long b,long long& x,long long& y)
{
  long long d = a;
  if(b != 0){
    d = extgcd(b,a%b,y,x);
    y -= (a/b)*x;
  }
  else
    x = 1,y = 0;
  return d;
}

long long mod_inv(long long a,long long m)
{
  long long x,y;
  extgcd(a,m,x,y);
  return (m+x%m)%m;
}

const int MAXnCk = 400001;
ll fact[MAXnCk+1], fact_inv[MAXnCk+1];
void init_nCk(){
  fact[0] = fact_inv[0] = 1;
  REP(i,1,MAXnCk+1) {
    fact[i] = fact[i-1] * (ll)i % mod;
    fact_inv[i] = mod_inv(fact[i],mod);
  }
}

ll nCk(ll n,ll k){
  if( n < 0 || k < 0 || k > n ) return 0LL;
  if( n-k < k ) k = n-k;
  return fact_inv[k] * fact[n] % mod * fact_inv[n-k] % mod;
}

ll modmultiply(ll a,ll b) {
  ll c = mod;
  ll x = 0,y = a%c; 
  while(b > 0) {
    if(b%2 == 1) x = (x+y)%c; 
    y = (y*2)%c;
    b /= 2; 
  }
  return x%c;
}

ll modpow(ll x, ll y) {
    ll ret = 1;// ret = x^y%mod;
    while(y) {
        if(y&1)
            //ret = (ret*x)%mod;
            ret = modmultiply(ret, x);
        //x = (x*x)%mod;
        x = modmultiply(x, x);
        y >>= 1;
    }
    return ret;
}



ll N, M;




void solve() {
  if( M > N ) { puts("0"); return; }
  ll n = N;
  ll k = M;
  ll v2 = 0;
  REP(i,1,k) {
    ll coef1 = 1;
    if( !( i & 1 ) ) coef1 = -1;
    ll coef2 = nCk(k,i);
    ll coef3 = modpow(k-i,n);
    v2 = ( v2 + ( ( ( coef1 * coef2 ) % mod ) * coef3 ) % mod );
    while( v2 < 0LL ) ( v2 += mod ) %= mod;
    //cout << "i = " << i << ", " << coef1 << " x " << coef2 << " x " << coef3 << endl;
  }
  v2 = ( modpow(k,n) - v2 ) % mod;
  while( v2 < 0LL ) ( v2 += mod ) %= mod;
  cout << v2 << endl;
}

int main() {
  init_nCk();
  int n = 7;
  int k = 3;
  ll v1 = 0;
  /*
  REP(i,1,k+1) {
    //ll coef1 = modpow(-1,k-i);
    ll coef1 = 1;
    rep(_,k-i) coef1 = coef1 * -1;
    ll coef2 = nCk(k,i);
    ll coef3 = modpow(i,n);
    v1 = ( v1 + ( ( ( coef1 * coef2 ) % mod ) * coef3 ) % mod );
    cout << "i = " << i << ", " << coef1 << " x " << coef2 << " x " << coef3 << endl;
  }
  cout << "v1 = " << v1 << endl;
  ll v2 = 0;
  REP(i,1,k) {
    ll coef1 = 1;
    if( !( i & 1 ) ) coef1 = -1;
    ll coef2 = nCk(k,i);
    ll coef3 = modpow(k-i,n);
    v2 = ( v2 + ( ( ( coef1 * coef2 ) % mod ) * coef3 ) % mod );
    cout << "i = " << i << ", " << coef1 << " x " << coef2 << " x " << coef3 << endl;
  }
  v2 = modpow(k,n) - v2;
  cout << "v2 = " << v2 << endl;
  */
  cin >> N >> M;
  solve();
  return 0;
}
0