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 |
|
|
|
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 |