結果

問題 No.389 ロジックパズルの組み合わせ
ユーザー furu_tuwwfuru_tuww
提出日時 2016-07-08 23:16:17
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 828 bytes
コンパイル時間 392 ms
コンパイル使用メモリ 56,540 KB
実行使用メモリ 5,504 KB
最終ジャッジ日時 2024-10-13 06:40:50
合計ジャッジ時間 3,055 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 99
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:37:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   37 |   scanf("%d",&m);
      |   ~~~~~^~~~~~~~~

ソースコード

diff # 

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define mod 1000000007

ll mf[11111111];
ll fact(ll n){
  if(mf[n]) return mf[n];

  ll ret = 1;
  for(ll i = 1; i <= n; i++){
    ret *= i;
    ret %= mod;
  }
  return mf[n] = ret;
}
ll inv(ll x,ll m){
  ll ret = 1;
  ll k = x;
  for(ll i = m-2; i > 0; i>>=1){
    if(i&1){
      ret *= k;
      ret %= m;
    }
    k *= k;
    k %= m;
  }
  return ret;
}

int m;
int k;
int H[1111111];
int main(void){
  scanf("%d",&m);
  int sum = 0;
  for(k = 0; scanf("%d",H+k)!=EOF; k++) sum += H[k];

  if(sum == 0){
    puts("1");
  }else if(sum+k-1 > m){
    puts("NA");
  }else{
    ll ans = 0;
    ll x = m-(sum+k-1);
    ans += fact(x+k)*inv(fact(x)*fact(k)%mod,mod)%mod;
    ans %= mod;
    
    printf("%lld\n",ans);
  }
    
}
0