結果

問題 No.391 CODING WAR
ユーザー __NCAstar
提出日時 2020-06-28 22:05:51
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0