답안 #31419

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31419 2017-08-22T06:07:15 Z gs14004 카드 (kriii4_Z) C++14
100 / 100
549 ms 3276 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int MAXN = 3005;
const int mod = 1e9 + 7;

namespace fft{
	typedef complex<double> base;
	void fft(vector<base> &a, bool inv){
		int n = a.size(), j = 0;
		for(int i=1; i<n; i++){
			int bit = (n >> 1);
			while(j >= bit){
				j -= bit;
				bit >>= 1;
			}
			j += bit;
			if(i < j) swap(a[i], a[j]);
		}
		for(int i=2; i<=n; i<<=1){
			double ang = 2 * acos(-1) / i * (inv ? -1 : 1);
			base x(cos(ang), sin(ang));
			for(int j=0; j<n; j+=i){
				base y(1);
				for(int k=0; k<i/2; k++){
					base u = a[j+k], v = a[j+k+i/2] * y;
					a[j+k] = u+v;
					a[j+k+i/2] = u-v;
					y *= x;
				}
			}
		}
		if(inv) for(int i=0; i<n; i++) a[i] /= n;
	}

	vector<lint> multiply(vector<lint> &v, vector<lint> &w){
		vector<base> fv(v.begin(), v.end()), fw(w.begin(), w.end());
		int n = 1;
		while(n < max(v.size(), w.size())) n <<= 1;
		n <<= 1;
		fv.resize(n);
		fw.resize(n);
		fft(fv, 0);
		fft(fw, 0);
		for(int i=0; i<n; i++) fv[i] *= fw[i];
		fft(fv, 1);
		vector<lint> ret(n);
		for(int i=0; i<n; i++) ret[i] = round(fv[i].real());
		return ret;
	}
	vector<lint> multiply(vector<lint> &v, vector<lint> &w, lint mod){
		int n = 1;
		while(n < max(v.size(), w.size())) n <<= 1;
		n <<= 1;
		vector<base> v1(n), v2(n);
		vector<base> r1(n), r2(n);
		for(int i=0; i<v.size(); i++){
			v1[i] = base(v[i] >> 15, v[i] & 32767);
		}
		for(int i=0; i<w.size(); i++){
			v2[i] = base(w[i] >> 15, w[i] & 32767);
		}
		fft(v1, 0);
		fft(v2, 0);
		for(int i=0; i<n; i++){
			int j = (i ? (n - i) : i);
			base ans1 = (v1[i] + conj(v1[j])) * base(0.5, 0);
			base ans2 = (v1[i] - conj(v1[j])) * base(0, -0.5);
			base ans3 = (v2[i] + conj(v2[j])) * base(0.5, 0);
			base ans4 = (v2[i] - conj(v2[j])) * base(0, -0.5);
			r1[i] = (ans1 * ans3) + (ans1 * ans4) * base(0, 1);
			r2[i] = (ans2 * ans3) + (ans2 * ans4) * base(0, 1);
		}
		fft(r1, 1);
		fft(r2, 1);
		vector<lint> ret(n);
		for(int i=0; i<n; i++){
			lint av = (lint)round(r1[i].real());
			lint bv = (lint)round(r1[i].imag()) + (lint)round(r2[i].real());
			lint cv = (lint)round(r2[i].imag());
			av %= mod, bv %= mod, cv %= mod;
			ret[i] = (av << 30) + (bv << 15) + cv;
			ret[i] %= mod;
			ret[i] += mod;
			ret[i] %= mod;
		}
		return ret;
	}
}

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

lint fact[MAXN], invf[MAXN];

lint bino(int x, int y){
	return fact[x] * (invf[x-y] * invf[y] % mod) % mod;
}

int n, l;
int cnt[MAXN];
lint dp[12][MAXN], func[MAXN];

vector<lint> solve(int x, int c){
	if(c == 0){
		vector<lint> ret(l + 1);
		ret[0] = 1;
		return ret;
	}
	if(c % 2 == 1){
		vector<lint> a = solve(x, c-1);
		vector<lint> b;
		for(int i=0; i<=l; i++){
			a[i] = (a[i] * invf[i]) % mod;
			b.push_back(i < x ? 0 : invf[i]);
		}
		auto ret = fft::multiply(a, b, mod);
		ret.resize(l + 1);
		for(int i=0; i<=l; i++){
			ret[i] %= mod;
			ret[i] *= fact[i];
			ret[i] %= mod;
		}
		return ret;
	}
	else{
		auto tmp = solve(x, c / 2);
		for(int i=0; i<=l; i++) tmp[i] = (tmp[i] * invf[i]) % mod;
		auto ret = fft::multiply(tmp, tmp, mod);
		ret.resize(l + 1);
		for(int i=0; i<=l; i++){
			ret[i] %= mod;
			ret[i] *= fact[i];
			ret[i] %= mod;
		}
		return ret;
	}
}

int main(){
	fact[0] = invf[0] = 1;
	for(int i=1; i<MAXN; i++){
		fact[i] = fact[i-1] * i % mod;
		invf[i] = ipow(fact[i], mod - 2);
	}
	cin >> n >> l;
	for(int i=0; i<n; i++){
		int x;
		cin >> x;
		cnt[x]++;
	}
	dp[0][0] = 1;
	for(int i=0; i<=10; i++){
		vector<lint> func = solve(i, cnt[i]);
		vector<lint> a, b;
		for(int j=0; j<=l; j++){
			a.push_back(func[j] * invf[j] % mod);
			b.push_back(dp[i][j] * invf[j] % mod);
		}
		auto ret = fft::multiply(a, b, mod);
		for(int j=0; j<=l; j++) dp[i+1][j] = ((ret[j] % mod) * fact[j] % mod);
	}
	dp[11][l] *= ipow(ipow(n, l), mod - 2);
	dp[11][l] %= mod;
	cout << dp[11][l];
}

Compilation message

Z.cpp: In function 'std::vector<long long int> fft::multiply(std::vector<long long int>&, std::vector<long long int>&)':
Z.cpp:40:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(n < max(v.size(), w.size())) n <<= 1;
           ^
Z.cpp: In function 'std::vector<long long int> fft::multiply(std::vector<long long int>&, std::vector<long long int>&, lint)':
Z.cpp:54:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(n < max(v.size(), w.size())) n <<= 1;
           ^
Z.cpp:58:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size(); i++){
                 ^
Z.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<w.size(); i++){
                 ^
# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 3212 KB Output is correct
2 Correct 183 ms 3212 KB Output is correct
3 Correct 146 ms 3276 KB Output is correct
4 Correct 183 ms 3276 KB Output is correct
5 Correct 179 ms 3276 KB Output is correct
6 Correct 166 ms 3276 KB Output is correct
7 Correct 163 ms 3212 KB Output is correct
8 Correct 186 ms 3276 KB Output is correct
9 Correct 159 ms 3276 KB Output is correct
10 Correct 173 ms 3276 KB Output is correct
11 Correct 173 ms 3276 KB Output is correct
12 Correct 179 ms 3192 KB Output is correct
13 Correct 193 ms 3212 KB Output is correct
14 Correct 186 ms 3276 KB Output is correct
15 Correct 199 ms 3276 KB Output is correct
16 Correct 206 ms 3276 KB Output is correct
17 Correct 199 ms 3276 KB Output is correct
18 Correct 233 ms 3212 KB Output is correct
19 Correct 176 ms 3276 KB Output is correct
20 Correct 196 ms 3276 KB Output is correct
21 Correct 136 ms 3232 KB Output is correct
22 Correct 129 ms 3276 KB Output is correct
23 Correct 119 ms 3212 KB Output is correct
24 Correct 136 ms 3236 KB Output is correct
25 Correct 123 ms 3276 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 239 ms 3276 KB Output is correct
2 Correct 206 ms 3276 KB Output is correct
3 Correct 379 ms 3276 KB Output is correct
4 Correct 433 ms 3276 KB Output is correct
5 Correct 299 ms 3276 KB Output is correct
6 Correct 423 ms 3276 KB Output is correct
7 Correct 466 ms 3276 KB Output is correct
8 Correct 399 ms 3276 KB Output is correct
9 Correct 106 ms 3276 KB Output is correct
10 Correct 169 ms 3276 KB Output is correct
11 Correct 186 ms 3276 KB Output is correct
12 Correct 226 ms 3276 KB Output is correct
13 Correct 249 ms 3276 KB Output is correct
14 Correct 233 ms 3276 KB Output is correct
15 Correct 323 ms 3276 KB Output is correct
16 Correct 179 ms 3276 KB Output is correct
17 Correct 159 ms 3276 KB Output is correct
18 Correct 446 ms 3276 KB Output is correct
19 Correct 449 ms 3276 KB Output is correct
20 Correct 549 ms 3276 KB Output is correct