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

提出ソース

結果

問題	No.389 ロジックパズルの組み合わせ
ユーザー	femto
提出日時	2016-07-08 22:30:33
言語	C++11 (gcc 11.4.0)
結果	AC
実行時間	42 ms / 2,000 ms
コード長	3,079 bytes
コンパイル時間	838 ms
コンパイル使用メモリ	73,504 KB
実行使用メモリ	13,540 KB
最終ジャッジ日時	2024-04-21 05:59:35
合計ジャッジ時間	5,384 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	19 ms 10,880 KB
testcase_01	AC	1 ms 5,376 KB
testcase_02	AC	19 ms 10,880 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	19 ms 11,008 KB
testcase_05	AC	1 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	1 ms 5,376 KB
testcase_08	AC	1 ms 5,376 KB
testcase_09	AC	22 ms 11,492 KB
testcase_10	AC	19 ms 11,264 KB
testcase_11	AC	21 ms 11,492 KB
testcase_12	AC	19 ms 11,264 KB
testcase_13	AC	28 ms 12,516 KB
testcase_14	AC	23 ms 11,496 KB
testcase_15	AC	19 ms 11,136 KB
testcase_16	AC	19 ms 11,392 KB
testcase_17	AC	20 ms 11,364 KB
testcase_18	AC	40 ms 13,540 KB
testcase_19	AC	19 ms 10,880 KB
testcase_20	AC	18 ms 10,880 KB
testcase_21	AC	18 ms 10,880 KB
testcase_22	AC	18 ms 10,880 KB
testcase_23	AC	18 ms 10,880 KB
testcase_24	AC	18 ms 10,880 KB
testcase_25	AC	18 ms 11,008 KB
testcase_26	AC	17 ms 11,008 KB
testcase_27	AC	19 ms 10,880 KB
testcase_28	AC	18 ms 10,880 KB
testcase_29	AC	18 ms 10,880 KB
testcase_30	AC	19 ms 10,880 KB
testcase_31	AC	18 ms 11,008 KB
testcase_32	AC	17 ms 10,880 KB
testcase_33	AC	18 ms 10,880 KB
testcase_34	AC	19 ms 11,008 KB
testcase_35	AC	19 ms 10,880 KB
testcase_36	AC	19 ms 11,008 KB
testcase_37	AC	18 ms 10,880 KB
testcase_38	AC	19 ms 10,880 KB
testcase_39	AC	19 ms 10,880 KB
testcase_40	AC	18 ms 10,880 KB
testcase_41	AC	18 ms 11,008 KB
testcase_42	AC	19 ms 10,880 KB
testcase_43	AC	18 ms 10,880 KB
testcase_44	AC	18 ms 10,880 KB
testcase_45	AC	18 ms 10,880 KB
testcase_46	AC	19 ms 10,880 KB
testcase_47	AC	18 ms 11,008 KB
testcase_48	AC	19 ms 10,880 KB
testcase_49	AC	23 ms 7,400 KB
testcase_50	AC	3 ms 5,376 KB
testcase_51	AC	2 ms 5,376 KB
testcase_52	AC	5 ms 5,376 KB
testcase_53	AC	4 ms 5,376 KB
testcase_54	AC	6 ms 5,376 KB
testcase_55	AC	2 ms 5,376 KB
testcase_56	AC	3 ms 5,376 KB
testcase_57	AC	11 ms 5,376 KB
testcase_58	AC	20 ms 7,268 KB
testcase_59	AC	14 ms 5,376 KB
testcase_60	AC	7 ms 5,376 KB
testcase_61	AC	30 ms 7,524 KB
testcase_62	AC	7 ms 5,376 KB
testcase_63	AC	20 ms 7,392 KB
testcase_64	AC	6 ms 5,376 KB
testcase_65	AC	4 ms 5,376 KB
testcase_66	AC	8 ms 5,376 KB
testcase_67	AC	7 ms 5,376 KB
testcase_68	AC	7 ms 5,376 KB
testcase_69	AC	19 ms 11,008 KB
testcase_70	AC	18 ms 11,008 KB
testcase_71	AC	19 ms 10,880 KB
testcase_72	AC	19 ms 10,880 KB
testcase_73	AC	18 ms 11,008 KB
testcase_74	AC	17 ms 10,880 KB
testcase_75	AC	18 ms 10,880 KB
testcase_76	AC	19 ms 11,008 KB
testcase_77	AC	19 ms 10,880 KB
testcase_78	AC	19 ms 10,880 KB
testcase_79	AC	19 ms 10,880 KB
testcase_80	AC	18 ms 10,880 KB
testcase_81	AC	18 ms 10,880 KB
testcase_82	AC	18 ms 10,880 KB
testcase_83	AC	19 ms 10,880 KB
testcase_84	AC	18 ms 10,880 KB
testcase_85	AC	18 ms 11,008 KB
testcase_86	AC	19 ms 10,880 KB
testcase_87	AC	16 ms 10,880 KB
testcase_88	AC	18 ms 10,880 KB
testcase_89	AC	25 ms 11,876 KB
testcase_90	AC	32 ms 12,644 KB
testcase_91	AC	42 ms 13,540 KB
testcase_92	AC	22 ms 11,364 KB
testcase_93	AC	30 ms 12,768 KB
testcase_94	AC	18 ms 11,008 KB
testcase_95	AC	32 ms 12,644 KB
testcase_96	AC	31 ms 12,260 KB
testcase_97	AC	27 ms 12,388 KB
testcase_98	AC	22 ms 11,616 KB

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

ソースコード

raw source code

#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;
typedef long long ll;

const int mod = 1000000007; // assert mod is prime

template<int M>
struct Mint {
	int x;
	Mint() : x(0) {}
	Mint(int y) : x(y >= 0 ? y % M : M - (-y) % M) {}
	Mint &operator += (const Mint &rhs) { if((x += rhs.x) >= M) x -= M; return *this; }
	Mint &operator -= (const Mint &rhs) { if((x += M - rhs.x) >= M) x -= M; return *this; }
	Mint &operator *= (const Mint &rhs) { x = 1LL * x*rhs.x % M; return *this; }
	Mint &operator /= (const Mint &rhs) { x = (1LL * x*rhs.inv().x) % M; return *this; }
	Mint operator - () const { return Mint(-x); }
	Mint operator + (const Mint &rhs) const { return Mint(*this) += rhs; }
	Mint operator - (const Mint &rhs) const { return Mint(*this) -= rhs; }
	Mint operator * (const Mint &rhs) const { return Mint(*this) *= rhs; }
	Mint operator / (const Mint &rhs) const { return Mint(*this) /= rhs; }
	bool operator < (const Mint &rhs) const { return x < rhs.x; }
	Mint inv() const {
		signed a = x, b = M, u = 1, v = 0, t;
		while(b) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
		return Mint(u);
	}
	Mint pow(long long t) const {
		Mint e = *this, res = 1;
		for(; t; e *= e, t >>= 1) if(t & 1) res *= e;
		return res;
	}
};
template <int M>
ostream &operator << (ostream &os, const Mint<M> &rhs) {
	return os << rhs.x;
}
template <int M>
istream &operator >> (istream &is, Mint<M> &rhs) {
	long long s; is >> s; rhs = Mint<M>(s); return is;
};

using mint = Mint<mod>;


ll modpow(ll x, ll y, ll m) {
	if(y == 0) return 1;
	ll res = modpow(x, y / 2, m);
	return res * res % m * (y & 1 ? x : 1) % m;
}

ll modinv(ll x, ll m) {
	return modpow(x, m - 2, m);
}

struct Comb {
	int sz;
	vector<mint> mfact, mfinv;
	Comb(int N) : sz(min(N, int(mod) - 1)), mfact(sz + 1), mfinv(sz + 1) {
		for(int i = 0; i <= sz; i++) mfact[i] = (i == 0 ? 1 : mfact[i - 1] * i);
		mfinv[sz] = mfact[sz].inv();
		for(int i = sz; i >= 1; i--) mfinv[i - 1] = mfinv[i] * i;
	}
	mint fact(int n, int& e) { // e に p の指数が入る
		// Wilson の定理
		e = 0;
		if(n <= sz) return mfact[n];
		mint res = fact(n / mod, e);
		e += n / mod;
		if(n / mod % 2 != 0) return -res * mfact[n % mod];
		return res * mfact[n % mod];
	}
	mint nPr(int n, int r) {
		int e; return fact(n, e) / fact(n - r, e);
	}
	mint nCr(int n, int r) {
		// Lucus の定理
		assert(n <= sz);
		if(n >= mod) return nCr(n%mod, r%mod) * nCr(n / mod, r / mod);
		return r > n ? 0 : mfact[n] * mfinv[n - r] * mfinv[r];
	}
	mint nHr(int n, int r) {
		return r == 0 ? 1 : nCr(n + r - 1, r);
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	ll M;
	cin >> M;

	vector<ll> v;
	ll H, sum = 0;
	while(cin >> H) {
		v.push_back(H);
		sum += H;
	}

	if(v[0] == 0) {
		cout << 1 << endl;
		return 0;
	}

	if(M < sum + v.size() - 1) {
		cout << "NA" << endl;
		return 0;
	}

	ll rem = M - sum - (v.size() - 1);
	//cerr << rem << endl;
	Comb C(1000010);
	cout << C.nHr(v.size() + 1, rem) << endl;
}

yukicoder

結果

テストケース

ソースコード