#114995 (C++11) No.389 ロジックパズルの組み合わせ

提出ソース

結果

問題	No.389 ロジックパズルの組み合わせ
ユーザー	uenoku
提出日時	2016-09-05 22:13:56
言語	C++11 (gcc 13.3.0)
結果	AC
実行時間	230 ms / 2,000 ms
コード長	3,489 bytes
コンパイル時間	1,274 ms
コンパイル使用メモリ	100,724 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-15 20:29:13
合計ジャッジ時間	6,434 ms
ジャッジサーバーID （参考情報）	judge3 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,820 KB
testcase_01	AC	1 ms 6,820 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,816 KB
testcase_04	AC	1 ms 6,816 KB
testcase_05	AC	2 ms 6,816 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	1 ms 6,816 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	28 ms 6,820 KB
testcase_10	AC	22 ms 6,820 KB
testcase_11	AC	40 ms 6,820 KB
testcase_12	AC	19 ms 6,816 KB
testcase_13	AC	121 ms 6,816 KB
testcase_14	AC	41 ms 6,820 KB
testcase_15	AC	14 ms 6,820 KB
testcase_16	AC	20 ms 6,816 KB
testcase_17	AC	35 ms 6,816 KB
testcase_18	AC	225 ms 6,816 KB
testcase_19	AC	1 ms 6,816 KB
testcase_20	AC	2 ms 6,816 KB
testcase_21	AC	2 ms 6,820 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	2 ms 6,816 KB
testcase_24	AC	2 ms 6,816 KB
testcase_25	AC	2 ms 6,820 KB
testcase_26	AC	1 ms 6,816 KB
testcase_27	AC	2 ms 6,816 KB
testcase_28	AC	1 ms 6,820 KB
testcase_29	AC	2 ms 6,816 KB
testcase_30	AC	1 ms 6,816 KB
testcase_31	AC	2 ms 6,820 KB
testcase_32	AC	1 ms 6,820 KB
testcase_33	AC	2 ms 6,816 KB
testcase_34	AC	2 ms 6,820 KB
testcase_35	AC	2 ms 6,820 KB
testcase_36	AC	2 ms 6,820 KB
testcase_37	AC	2 ms 6,820 KB
testcase_38	AC	2 ms 6,816 KB
testcase_39	AC	1 ms 6,816 KB
testcase_40	AC	1 ms 6,820 KB
testcase_41	AC	2 ms 6,816 KB
testcase_42	AC	1 ms 6,816 KB
testcase_43	AC	1 ms 6,816 KB
testcase_44	AC	1 ms 6,820 KB
testcase_45	AC	1 ms 6,816 KB
testcase_46	AC	1 ms 6,820 KB
testcase_47	AC	2 ms 6,820 KB
testcase_48	AC	2 ms 6,816 KB
testcase_49	AC	48 ms 6,820 KB
testcase_50	AC	4 ms 6,820 KB
testcase_51	AC	4 ms 6,816 KB
testcase_52	AC	10 ms 6,816 KB
testcase_53	AC	5 ms 6,816 KB
testcase_54	AC	12 ms 6,816 KB
testcase_55	AC	2 ms 6,820 KB
testcase_56	AC	5 ms 6,816 KB
testcase_57	AC	20 ms 6,816 KB
testcase_58	AC	38 ms 6,816 KB
testcase_59	AC	32 ms 6,820 KB
testcase_60	AC	15 ms 6,820 KB
testcase_61	AC	67 ms 6,816 KB
testcase_62	AC	14 ms 6,816 KB
testcase_63	AC	40 ms 6,816 KB
testcase_64	AC	12 ms 6,816 KB
testcase_65	AC	8 ms 6,816 KB
testcase_66	AC	13 ms 6,820 KB
testcase_67	AC	12 ms 6,816 KB
testcase_68	AC	12 ms 6,820 KB
testcase_69	AC	2 ms 6,816 KB
testcase_70	AC	1 ms 6,816 KB
testcase_71	AC	2 ms 6,820 KB
testcase_72	AC	2 ms 6,816 KB
testcase_73	AC	1 ms 6,820 KB
testcase_74	AC	2 ms 6,820 KB
testcase_75	AC	1 ms 6,820 KB
testcase_76	AC	1 ms 6,820 KB
testcase_77	AC	1 ms 6,820 KB
testcase_78	AC	2 ms 6,820 KB
testcase_79	AC	2 ms 6,820 KB
testcase_80	AC	2 ms 6,820 KB
testcase_81	AC	1 ms 6,820 KB
testcase_82	AC	1 ms 6,820 KB
testcase_83	AC	2 ms 6,816 KB
testcase_84	AC	1 ms 6,816 KB
testcase_85	AC	1 ms 6,816 KB
testcase_86	AC	2 ms 6,820 KB
testcase_87	AC	2 ms 6,816 KB
testcase_88	AC	2 ms 6,820 KB
testcase_89	AC	80 ms 6,816 KB
testcase_90	AC	130 ms 6,816 KB
testcase_91	AC	230 ms 6,816 KB
testcase_92	AC	34 ms 6,816 KB
testcase_93	AC	145 ms 6,816 KB
testcase_94	AC	4 ms 6,820 KB
testcase_95	AC	153 ms 6,816 KB
testcase_96	AC	118 ms 6,816 KB
testcase_97	AC	109 ms 6,816 KB
testcase_98	AC	51 ms 6,816 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>
#include "math.h"
#include <complex>
#include <iomanip>
#include <map>
#define ifor(i,a,b) for (int i=(a);i<(b);i++)
#define rfor(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define rep(i,n) for (int i=0;i<(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
using namespace std;
typedef long double ld;
typedef long long int  lli;
typedef complex <double> P;
const double eps = 1e-11;
int vex[4]={1,0,-1,0};
int vey[4]={0,1,0,-1};
typedef vector<double> Vec;
typedef vector<int> vec;
typedef vector<Vec> MAT;
typedef vector<vec> mat;
lli MOD=1000000007;
//Ax=bをとくAは正方行列
//rankA<=min(m,n)ならば配列０のvecが帰る
Vec gauss_jordan(const MAT& A,const Vec&b){
	int n  = A.size();
	MAT B (n,Vec(n+1));
	rep(i,n)rep(j,n)B[i][j]=A[i][j];
	rep(i,n)B[i][n]=b[i];

	rep(i,n){
		int pivot = i;
		for(int j= i;j<n;j++){
			if(abs(B[j][i])>abs(B[pivot][i]))pivot = j;
		}

		swap(B[i],B[pivot]);
		if(abs(B[i][i])<eps)return Vec();
    //B_i_i成分が0であるつまり階数が
		for(int j =i +1 ;j<=n;j++)B[i][j]/=B[i][i];
		rep(j,n){
			if(i!=j)
				for(int k = i+1;k<=n;k++){
					B[j][k] -=B[j][i]*B[i][k];
				}
		}
	}
	Vec x(n);
	for(int i =0;i<n;i++){
		x[i]= B[i][n];
	}
	return x;


}
double det(const MAT& A){
	int n = A.size();
	MAT B (n,Vec(n));
	rep(i,n)rep(j,n)B[i][j]=A[i][j];
	double ans = 1;
	rep(i,n){
		int pivot = i;
		for(int j=i;j<n;j++){
			if(abs(B[j][i])>abs(B[pivot][i]))pivot = j;
		}
		if(i!=pivot)ans *= -1;
		swap(B[i],B[pivot]);
		if(abs(B[i][i])<eps)
			return 0;
		ans *= B[i][i];
		for(int j =i +1 ;j<n;j++)B[i][j]/=B[i][i];
		rep(j,n){
			if(i!=j)
				for(int k = i+1;k<n;k++){
					B[j][k] -=B[j][i]*B[i][k];
				}
		}
	}
	return ans;

}
int  rank(const MAT& A){
	int n = A.size();
	MAT B (n,Vec(n));
	rep(i,n)rep(j,n)B[i][j]=A[i][j];

	rep(i,n){
		int pivot = i;
		for(int j=i;j<n;j++){
			if(abs(B[j][i])>abs(B[pivot][i]))pivot = j;
		}
		swap(B[i],B[pivot]);
		if(abs(B[i][i])<eps)return i;
		for(int j =i +1 ;j<n;j++)B[i][j]/=B[i][i];
		rep(j,n){
			if(i!=j)
				for(int k = i+1;k<n;k++){
					B[j][k] -=B[j][i]*B[i][k];
				}
		}
	}
	return n;
}
lli euler(lli m){
	vector<int> p;
	lli M = m;
	for(int i = 2;i<=m;i++){
		if(m%i==0){
			p.push_back(i);
			while(m%i==0)m/=i;
		}
		if(M<i*i&&p.size()==0){
			p.push_back(M);
			break;
		}

	}
	lli ans = M;
	rep(i,p.size()){
		//cout << p[i]<<endl;
		ans = ans * (p[i]-1)/p[i];
	}
	return ans;
}
lli powm(lli a,lli p,lli mod){
	lli ans =1;
	while(p>0){
		if(p&1)ans=(ans*a) % mod;
		a=(a*a)%mod;
		p >>=1;
	}
	return ans%mod;
}
lli inv(lli a,lli mod){
	return  powm(a,euler(mod)-1,mod);
}
lli inv(lli a){
	return  powm(a,MOD-2,MOD);
}
lli gcd(lli A,lli B){
	if(A%B==0)return B;
	else return gcd(B,A%B);
}
mat mul_mat_mod(mat A,mat B,lli m){
	int n = A.size();
	mat C (n,vec(n));
	rep(i,n)rep(j,n)rep(k,n){
		C[i][j]+=A[i][k]*B[k][j] %m;
		C[i][j]%=m;
	}
	return C;
}
mat pow_mat(mat A,lli p,lli mod){
	int n= A.size();
	mat B = mat(n,vec(n));
	while(p>0){
		if(p&1){
			B=mul_mat_mod(A,B,mod);
		}
		A = mul_mat_mod(A,A,mod);
		p>>=1;
	}
	return B;
}
lli comb(lli a,lli b ){
	lli ans =1;
	rep(i,b){
		ans = ans %MOD* (a-i)%MOD*inv(b-i)%MOD;
	}
	return ans ;
}
int main(){
 lli M;
  cin >> M;
  lli k =0,h;
  lli s = 0;
  while(cin >> h){
    k++;
    s += h;
  }
  s += k-1;
  if(k==1&&h==0){cout<<1<<endl;return 0;}
  if(M<s)cout<<"NA"<<endl;
  else cout<<comb(M-s+k,k)<<endl;
}

yukicoder

結果

テストケース

ソースコード