結果

問題 No.389 ロジックパズルの組み合わせ
ユーザー furu_tuww
提出日時 2016-07-08 23:03:18
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 971 bytes
コンパイル時間 511 ms
コンパイル使用メモリ 56,272 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-10-13 06:28:43
合計ジャッジ時間 3,081 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 94 WA * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
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[1111111];
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 || sum+k-1 > m){
    puts("NA");
  }else{
    ll ans = 0;

    /*
    for(ll i = 0; i <= m-(sum+k-1); i++){
      ans +=  fact(i+k-1)*inv(fact(i)*fact(k-1)%mod,mod)%mod;
      ans %= mod;
      printf("%lld\n",i);
    }
    */
    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