結果

問題 No.1956 猫の額
ユーザー 37zigen
提出日時 2022-04-28 08:05:28
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,169 bytes
コンパイル時間 1,454 ms
コンパイル使用メモリ 90,352 KB
最終ジャッジ日時 2025-01-28 22:09:43
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 4 TLE * 15 MLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <limits>
#include <queue>
#include <vector>
#include <iostream>
#include <assert.h>

using namespace std;

const int NMAX = 100;
const int AMAX = 100000;
vector<long long> A;

int N, M, C, sumA;

long long powmod(long long a, long long n, long long p) {
	if (n == 0) return 1;
	return powmod(a * a % p, n / 2, p) * (n % 2 == 1 ? a : 1) % p;
}

long long inv(long long a, long long p) {
	return powmod(a, p - 2, p);
}

long long garner(vector<long long>& a, vector<long long>& mods, long long m) {
	int n = a.size();
	vector<long long> b; 
	auto gen_base = [&mods](long long mod) {
		vector<long long> base{ 1 };
		for (int j = 0; j < mods.size(); ++j) {
			base.push_back(base.back() * mods[j] % mod);
		}
		return base;
	};
	auto f = [&b] (vector<long long> base, long long mod) {
		long long x = 0;
		for (int j = 0; j < b.size(); ++j) {
			x = (x + b[j] * base[j]) % mod;
		}
		return x;
	};
	for (int i = 0; i < n; ++i) {
		auto base = gen_base(mods[i]);
		b.push_back(inv(base[i], mods[i]) * (-f(base, mods[i]) + a[i]) % mods[i]);
		if (b[i] < 0) b[i] += mods[i];
	}
	return f(gen_base(m), m);

}

void calc(vector<int> &a, vector<long long>& fac, vector<long long>& ifac, vector<long long>& inv, long long mod, vector<long long> &ans) {
	vector<long long> f(sumA + 1);
	f[0] = 1;
	for (long long i : a) {
		vector<long long> nf(sumA + 1);
		for (long long k = 0; k <= sumA; ++k) {
			if (f[k] == 0) continue;
			for (long long Aj : A) if (k + i * Aj <= sumA) {
				nf[k + i * Aj] += inv[i] * (i % 2 == 0 ? mod - 1 : 1) % mod * f[k] % mod;
				nf[k + i * Aj] %= mod;
			}
		}
		f = nf;
	}
	long long c = 1;
	for (int i = 0; i < a.size(); ++i) {
		int j = i;
		while (j + 1 < a.size() && a[i] == a[j + 1]) ++j;
		c = c * ifac[j - i + 1] % mod;
		i = j;
	}
	for (int i = 0; i < ans.size(); ++i) ans[i] = (ans[i] + c * f[i]) % mod;
}


void dfs(int add, int res, vector<int> &a, long long mod, vector<long long> &fac, vector<long long> &ifac, vector<long long> &inv, vector<long long> &ans) {
	if (res == 0) calc(a, fac, ifac, inv, mod, ans);
	else if (res > 0) {
		for (int nadd = add; nadd <= C; ++nadd) {
			a.push_back(nadd);
			dfs(nadd, res - nadd, a, mod, fac, ifac, inv, ans);
			a.pop_back();
		}
	}
}

int main() {
	cin >> N >> M >> C;
	A.resize(N);
	for (int i = 0; i < N; ++i) cin >> A[i];
		
	for (int a: A) sumA += a;
	vector<long long> mods{ (long long)1e9 + 9, (long long)1e9 + 7, (long long)1e9 + 21, (long long)1e9 + 33};
	vector<vector<long long>> x(4, vector<long long>(sumA + 1));
	for (int i = 0; i < mods.size(); ++i) {
		long long mod = mods[i];
		vector<long long> fac{ 1, 1 };
		vector<long long> ifac{ 1, 1 };
		vector<long long> inv{ 1, 1 };
		for (int j = 2; j < 1000; ++j) {
			fac.push_back(fac.back() * j % mod);
			inv.push_back(mod - mod / j * inv[mod % j] % mod);
			ifac.push_back(ifac.back() * inv[j] % mod);
		}
		vector<int> a;
		dfs(1, C, a, mod, fac, ifac, inv, x[i]);
	}
	for (int i = 0; i <= sumA; ++i) {
		vector<long long> a;
		for (int j = 0; j < mods.size(); ++j) a.push_back(x[j][i]);
		long long ans = garner(a, mods, M);
		cout << ans << (i == sumA ? "\n" : " ");
	}
}
0