結果

問題 No.389 ロジックパズルの組み合わせ
コンテスト
ユーザー tatuyan_edson
提出日時 2016-03-21 15:26:24
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 167 ms / 2,000 ms
コード長 1,122 bytes
コンパイル時間 635 ms
コンパイル使用メモリ 22,656 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-01 12:24:25
合計ジャッジ時間 6,141 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 99
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:14:3: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |   scanf("%llu%*c",&M);
      |   ^~~~~~~~~~~~~~~~~~~
main.c:16:5: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |     scanf("%llu%c",&temp,&c);
      |     ^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>

unsigned long long const modnum=1000000007;

unsigned long long invdiv(unsigned long long p);

int main(void){
  unsigned long long M,S=0,n=0,ans=1;
  unsigned long long alls,rest,temp;
  unsigned long long i,j,k;
  char c;

  scanf("%llu%*c",&M);
  do{
    scanf("%llu%c",&temp,&c);
    S+=temp;
    n++;
  }while(c==' ');

  if(S+n-1>M) puts("NA");
  else if(S==0) puts("1");
  else{
    alls=M-S+1;
    rest=alls-n;

    for(i=1;i<=alls;i++){
      ans*=i;
      ans%=modnum;
    }
    for(i=1;i<=rest;i++){
      ans*=invdiv(i);
      ans%=modnum;
    }
    for(i=1;i<=n;i++){
      ans*=invdiv(i);
      ans%=modnum;
    }
    printf("%llu\n",ans);
  }
  return 0;
}


unsigned long long invdiv(unsigned long long p) {
	unsigned long long r[3], q;
	unsigned long long x[3];
	div_t clc;

	r[0] = p;
	r[1] = modnum;

	x[0] = 1;
	x[1] = 0;

	do {
		clc = div(r[0], r[1]);
		q = clc.quot;
		r[2] = clc.rem;
		while(x[0] < q * x[1]) x[0] += modnum;
		x[2] = (x[0] - q * x[1]) % modnum;

		r[0] = r[1];
		r[1] = r[2];

		x[0] = x[1];
		x[1] = x[2];
	} while(r[2] > 1);
	return x[2];
}
0