답안 #31412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
31412 2017-08-21T15:26:58 Z gs14004 카드 (kriii4_Z) C++14
13 / 100
1000 ms 2656 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> &v, bool inv){
		int n = v.size();
		vector<base> w(n/2), aux(n);
		for(int i=0; i<n/2; i++){
			int k = i&-i;
			if(i == k){
				double ang = 2 * M_PI * i / n;
				if(inv) ang *= -1;
				w[i] = base(cos(ang), sin(ang));
			}
			else w[i] = w[i-k] * w[k];
		}
		for(int i=n/2; i; i>>=1){
			aux = v;
			for(int k=0; 2*k<n; k+=i){
				for(int j=0; j<i; j++){
					base a = aux[2*k + j], b = aux[2*k + j + i] * w[k];
					v[k + j] = a + b;
					v[k + j + n/2] = a - b;
				}
			}
		}
		if(inv){
			for(int i=0; i<n; i++){
				v[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, int b){
		vector<lint> ans(v.size());
		int l = v.size() - 1;
		for(int i=0; i<=l; i++){
			for(int j=0; i+j<=l; j++){
				ans[i+j] += v[i] * w[j];
				ans[i+j] %= mod;
			}
		}
		return ans;
		int n = 1;
		while(n < max(v.size(), w.size())) n <<= 1;
		n <<= 1;
		vector<base> v1(n), v2(n), v3(n), v4(n), r1(n), r2(n), r3(n);
		for(int i=0; i<v.size(); i++){
			v1[i] = base(v[i] / b, 0);
			v2[i] = base(v[i] % b, 0);
		}
		for(int i=0; i<w.size(); i++){
			v3[i] = base(w[i] / b, 0);
			v4[i] = base(w[i] % b, 0);
		}
		fft(v1, 0);
		fft(v2, 0);
		fft(v3, 0);
		fft(v4, 0);
		for(int i=0; i<n; i++){
			r1[i] = v1[i] * v3[i];
			r2[i] = v1[i] * v4[i] + v2[i] * v3[i];
			r3[i] = v2[i] * v4[i];
		}
		fft(r1, 1);
		fft(r2, 1);
		fft(r3, 1);
		vector<lint> ret(n);
		for(int i=0; i<n; i++){
			ret[i] = (lint)round(r1[i].real()) * b * b + (lint)round(r2[i].real()) * b + (lint)round(r3[i].real());
		}
		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){
		auto tmp = solve(x, c-1);
		vector<lint> ret(l + 1);
		for(int i=0; i<=l; i++){
			for(int j=0; j<=i-x; j++){
				ret[i] += tmp[j] * bino(i, j) % mod;
			}
			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, 1<<15);
		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, 1<<15);
		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:41: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>&, int)':
Z.cpp:64:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(n < max(v.size(), w.size())) n <<= 1;
           ^
Z.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v.size(); i++){
                 ^
Z.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<w.size(); i++){
                 ^
# 결과 실행 시간 메모리 Grader output
1 Correct 619 ms 2648 KB Output is correct
2 Correct 693 ms 2640 KB Output is correct
3 Correct 429 ms 2652 KB Output is correct
4 Correct 653 ms 2640 KB Output is correct
5 Correct 553 ms 2576 KB Output is correct
6 Correct 583 ms 2652 KB Output is correct
7 Correct 546 ms 2576 KB Output is correct
8 Correct 636 ms 2652 KB Output is correct
9 Correct 616 ms 2648 KB Output is correct
10 Correct 523 ms 2572 KB Output is correct
11 Correct 559 ms 2568 KB Output is correct
12 Correct 469 ms 2568 KB Output is correct
13 Correct 656 ms 2568 KB Output is correct
14 Correct 809 ms 2640 KB Output is correct
15 Correct 683 ms 2576 KB Output is correct
16 Correct 559 ms 2652 KB Output is correct
17 Correct 759 ms 2640 KB Output is correct
18 Correct 649 ms 2652 KB Output is correct
19 Correct 696 ms 2640 KB Output is correct
20 Correct 656 ms 2652 KB Output is correct
21 Correct 549 ms 2652 KB Output is correct
22 Correct 586 ms 2652 KB Output is correct
23 Correct 469 ms 2640 KB Output is correct
24 Correct 559 ms 2640 KB Output is correct
25 Correct 606 ms 2652 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 2656 KB Output is correct
2 Correct 819 ms 2648 KB Output is correct
3 Execution timed out 1000 ms 2648 KB Execution timed out
4 Halted 0 ms 0 KB -