Submission #2276657


Source Code Expand

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
using namespace std;
typedef long long int llint;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
const int mod=1000000007;
const llint big=1e18+10;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-9;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
int LBI(vector<int>&ar,int in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
int UBI(vector<int>&ar,int in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
template <uint64_t MOD_ = 1000000007>
class mint_base
{
public:
	static constexpr auto MOD = MOD_;
	static_assert(!(MOD <= 2), "MOD cannot be below 2.");
	static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない
	static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない
	constexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept
	{auto v = *this;return v += other;}
	constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept
	{auto v = *this;return v -= other;}
	constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept
	{auto v = *this;return v *= other;}
	constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept
	{a += other.a;if (MOD <= a) { a -= MOD; };return *this;}
	constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept
	{if (a >= other.a) {a -= other.a;}else {a = (a + MOD) - other.a;}return *this;}
	constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept
	{a *= other.a;a %= MOD;return *this;}
	constexpr mint_base<MOD> operator+()const noexcept { return *this; }
	constexpr mint_base<MOD> operator-()const noexcept
	{return{ MOD - a, mod_value_tag{} };}
	constexpr mint_base<MOD>& operator++() noexcept
	{if (MOD <= ++a) { a = 0; };return *this;}
	constexpr mint_base<MOD>& operator--() noexcept
	{if (a <= 0) { a = MOD; };--a;return *this;}
	constexpr mint_base<MOD> operator++(int) noexcept
	{auto tmp = *this;++*this;return tmp;}
	constexpr mint_base<MOD> operator--(int) noexcept
	{auto tmp = *this;--*this;return tmp;}
	constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept
	{a = other.a;return *this;}
	constexpr explicit operator uint64_t()const noexcept
	{return a;}
	constexpr explicit operator unsigned()const noexcept
	{return (unsigned)a;}
	static constexpr uint64_t getmod() noexcept
	{return MOD;}
	constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {}
	constexpr mint_base()noexcept : a(0) {}
	struct mod_value_tag {};
	constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {}
private:
	uint64_t a;
};
//mint_base型のstreamへの出力
template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i)
{os << (uint64_t)i;return os;}
//mint_base型のstreamからの入力
template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i)
{uint64_t tmp;is >> tmp;i = tmp;return is;}
mint_base<> zyo(mint_base<> a,llint b){
	mint_base<> bgen=a,ans=1;
	for(int h=0;h<30;h++){
		if(b&(1<<h)){ans*=bgen;}
		bgen*=bgen;
	}
	return ans;
}
int main(void){
	int n,i,j,k,m;cin>>n;
	mint_base<> D;cin>>D;
	//dp[きたえない種類][決めた日数]で実家
	//nCr
	vector<int>a(n);
	static mint_base<> dp[31][901]={};
	dp[0][0]=1;
	mint_base<> ruikai[901]={};
	ruikai[0]=1;
	for(k=1;k<=900;k++){ruikai[k]=ruikai[k-1]*(D-k+1);}
	mint_base<> gruikai[901]={};
	for(k=0;k<=900;k++){gruikai[k]=zyo(ruikai[k],mod-2);}
	mint_base<> kai[901]={};
	kai[0]=1;
	for(k=1;k<=900;k++){kai[k]=kai[k-1]*k;}
	mint_base<> gkai[901]={};
	for(k=0;k<=900;k++){gkai[k]=zyo(kai[k],mod-2);}
	int wa=0;
	for(i=0;i<n;i++){
		int a;cin>>a;
		mint_base<> ddp[31][901]={};
		for(j=0;j<=i;j++){
			for(m=0;m<=wa;m++){
				ddp[j][m]=dp[j][m];
			}
		}
		for(j=0;j<a;j++){//j niti kitaeru
			for(k=0;k<=i;k++){//k syu kitaete nai
				for(m=0;m<=wa;m++){//m niti kimeta
					if((uint64_t)(D-m-j)<0){continue;}
					ddp[k+1][m+j]+=dp[k][m]*gruikai[m]*ruikai[m+j]*gkai[j];
				}
			}
		}
		swap(dp,ddp);
		wa+=a;
	}
	mint_base<> ans=0;
	for(k=0;k<=n;k++){
		for(m=0;m<=wa;m++){
			if(k%2==0){ans+=dp[k][m]*zyo(n-k,(uint64_t)D-m);}
			else{ans-=dp[k][m]*zyo(n-k,(uint64_t)D-m);}
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Submission Time
Task D - 天下一ボディービルコンテスト
User WA_TLE
Language C++14 (GCC 5.4.1)
Score 280
Code Size 5187 Byte
Status AC
Exec Time 74 ms
Memory 768 KB

Judge Result

Set Name level1 level2 level3
Score / Max Score 40 / 40 100 / 100 140 / 140
Status
AC × 27
AC × 50
AC × 74
Set Name Test Cases
level1 level1_max_0.txt, level1_maxrand_0.txt, level1_maxrand_1.txt, level1_maxrand_2.txt, level1_maxrand_3.txt, level1_maxrand_4.txt, level1_maxrand_5.txt, level1_maxrand_6.txt, level1_maxrand_7.txt, level1_maxrand_8.txt, level1_maxrand_9.txt, level1_min1_0.txt, level1_min2_0.txt, level1_min3_0.txt, level1_min4_0.txt, level1_rand_0.txt, level1_rand_1.txt, level1_rand_2.txt, level1_rand_3.txt, level1_rand_4.txt, level1_rand_5.txt, level1_rand_6.txt, level1_rand_7.txt, level1_rand_8.txt, level1_rand_9.txt, level1_sample1.txt, level1_sample2.txt
level2 level1_max_0.txt, level1_maxrand_0.txt, level1_maxrand_1.txt, level1_maxrand_2.txt, level1_maxrand_3.txt, level1_maxrand_4.txt, level1_maxrand_5.txt, level1_maxrand_6.txt, level1_maxrand_7.txt, level1_maxrand_8.txt, level1_maxrand_9.txt, level1_min1_0.txt, level1_min2_0.txt, level1_min3_0.txt, level1_min4_0.txt, level1_rand_0.txt, level1_rand_1.txt, level1_rand_2.txt, level1_rand_3.txt, level1_rand_4.txt, level1_rand_5.txt, level1_rand_6.txt, level1_rand_7.txt, level1_rand_8.txt, level1_rand_9.txt, level1_sample1.txt, level1_sample2.txt, level2_max_0.txt, level2_maxrand_0.txt, level2_maxrand_1.txt, level2_maxrand_2.txt, level2_maxrand_3.txt, level2_maxrand_4.txt, level2_maxrand_5.txt, level2_maxrand_6.txt, level2_maxrand_7.txt, level2_maxrand_8.txt, level2_maxrand_9.txt, level2_min1_0.txt, level2_min2_0.txt, level2_rand_0.txt, level2_rand_1.txt, level2_rand_2.txt, level2_rand_3.txt, level2_rand_4.txt, level2_rand_5.txt, level2_rand_6.txt, level2_rand_7.txt, level2_rand_8.txt, level2_rand_9.txt
level3 level1_max_0.txt, level1_maxrand_0.txt, level1_maxrand_1.txt, level1_maxrand_2.txt, level1_maxrand_3.txt, level1_maxrand_4.txt, level1_maxrand_5.txt, level1_maxrand_6.txt, level1_maxrand_7.txt, level1_maxrand_8.txt, level1_maxrand_9.txt, level1_min1_0.txt, level1_min2_0.txt, level1_min3_0.txt, level1_min4_0.txt, level1_rand_0.txt, level1_rand_1.txt, level1_rand_2.txt, level1_rand_3.txt, level1_rand_4.txt, level1_rand_5.txt, level1_rand_6.txt, level1_rand_7.txt, level1_rand_8.txt, level1_rand_9.txt, level1_sample1.txt, level1_sample2.txt, level2_max_0.txt, level2_maxrand_0.txt, level2_maxrand_1.txt, level2_maxrand_2.txt, level2_maxrand_3.txt, level2_maxrand_4.txt, level2_maxrand_5.txt, level2_maxrand_6.txt, level2_maxrand_7.txt, level2_maxrand_8.txt, level2_maxrand_9.txt, level2_min1_0.txt, level2_min2_0.txt, level2_rand_0.txt, level2_rand_1.txt, level2_rand_2.txt, level2_rand_3.txt, level2_rand_4.txt, level2_rand_5.txt, level2_rand_6.txt, level2_rand_7.txt, level2_rand_8.txt, level2_rand_9.txt, level3_max_0.txt, level3_maxrand_0.txt, level3_maxrand_1.txt, level3_maxrand_2.txt, level3_maxrand_3.txt, level3_maxrand_4.txt, level3_maxrand_5.txt, level3_maxrand_6.txt, level3_maxrand_7.txt, level3_maxrand_8.txt, level3_maxrand_9.txt, level3_min1_0.txt, level3_min2_0.txt, level3_rand_0.txt, level3_rand_1.txt, level3_rand_2.txt, level3_rand_3.txt, level3_rand_4.txt, level3_rand_5.txt, level3_rand_6.txt, level3_rand_7.txt, level3_rand_8.txt, level3_rand_9.txt, level3_sample3.txt
Case Name Status Exec Time Memory
level1_max_0.txt AC 2 ms 768 KB
level1_maxrand_0.txt AC 2 ms 640 KB
level1_maxrand_1.txt AC 2 ms 640 KB
level1_maxrand_2.txt AC 2 ms 768 KB
level1_maxrand_3.txt AC 2 ms 768 KB
level1_maxrand_4.txt AC 2 ms 768 KB
level1_maxrand_5.txt AC 2 ms 640 KB
level1_maxrand_6.txt AC 2 ms 768 KB
level1_maxrand_7.txt AC 2 ms 768 KB
level1_maxrand_8.txt AC 2 ms 768 KB
level1_maxrand_9.txt AC 2 ms 768 KB
level1_min1_0.txt AC 2 ms 768 KB
level1_min2_0.txt AC 2 ms 768 KB
level1_min3_0.txt AC 2 ms 768 KB
level1_min4_0.txt AC 2 ms 768 KB
level1_rand_0.txt AC 2 ms 640 KB
level1_rand_1.txt AC 2 ms 768 KB
level1_rand_2.txt AC 2 ms 768 KB
level1_rand_3.txt AC 2 ms 640 KB
level1_rand_4.txt AC 2 ms 768 KB
level1_rand_5.txt AC 2 ms 768 KB
level1_rand_6.txt AC 2 ms 768 KB
level1_rand_7.txt AC 2 ms 768 KB
level1_rand_8.txt AC 2 ms 640 KB
level1_rand_9.txt AC 2 ms 768 KB
level1_sample1.txt AC 2 ms 640 KB
level1_sample2.txt AC 2 ms 768 KB
level2_max_0.txt AC 2 ms 640 KB
level2_maxrand_0.txt AC 2 ms 768 KB
level2_maxrand_1.txt AC 2 ms 768 KB
level2_maxrand_2.txt AC 2 ms 768 KB
level2_maxrand_3.txt AC 2 ms 768 KB
level2_maxrand_4.txt AC 2 ms 768 KB
level2_maxrand_5.txt AC 2 ms 768 KB
level2_maxrand_6.txt AC 2 ms 768 KB
level2_maxrand_7.txt AC 2 ms 768 KB
level2_maxrand_8.txt AC 2 ms 640 KB
level2_maxrand_9.txt AC 2 ms 640 KB
level2_min1_0.txt AC 2 ms 640 KB
level2_min2_0.txt AC 2 ms 640 KB
level2_rand_0.txt AC 2 ms 640 KB
level2_rand_1.txt AC 2 ms 640 KB
level2_rand_2.txt AC 2 ms 640 KB
level2_rand_3.txt AC 2 ms 768 KB
level2_rand_4.txt AC 2 ms 640 KB
level2_rand_5.txt AC 2 ms 768 KB
level2_rand_6.txt AC 2 ms 768 KB
level2_rand_7.txt AC 2 ms 640 KB
level2_rand_8.txt AC 2 ms 768 KB
level2_rand_9.txt AC 2 ms 640 KB
level3_max_0.txt AC 74 ms 640 KB
level3_maxrand_0.txt AC 26 ms 768 KB
level3_maxrand_1.txt AC 20 ms 640 KB
level3_maxrand_2.txt AC 20 ms 640 KB
level3_maxrand_3.txt AC 23 ms 640 KB
level3_maxrand_4.txt AC 20 ms 768 KB
level3_maxrand_5.txt AC 28 ms 768 KB
level3_maxrand_6.txt AC 26 ms 640 KB
level3_maxrand_7.txt AC 21 ms 768 KB
level3_maxrand_8.txt AC 25 ms 640 KB
level3_maxrand_9.txt AC 20 ms 640 KB
level3_min1_0.txt AC 3 ms 768 KB
level3_min2_0.txt AC 2 ms 768 KB
level3_rand_0.txt AC 13 ms 768 KB
level3_rand_1.txt AC 10 ms 640 KB
level3_rand_2.txt AC 2 ms 768 KB
level3_rand_3.txt AC 4 ms 640 KB
level3_rand_4.txt AC 2 ms 768 KB
level3_rand_5.txt AC 5 ms 768 KB
level3_rand_6.txt AC 4 ms 640 KB
level3_rand_7.txt AC 8 ms 768 KB
level3_rand_8.txt AC 3 ms 768 KB
level3_rand_9.txt AC 2 ms 768 KB
level3_sample3.txt AC 3 ms 640 KB