Submission #491182

#TimeUsernameProblemLanguageResultExecution timeMemory
491182inksamuraiAnagramistica (COCI21_anagramistica)C++17
110 / 110
77 ms460 KiB
#include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() #define rep(i,n) for(int i=0;i<n;i++) #define crep(i,x,n) for(int i=x;i<n;i++) #define drep(i,n) for(int i=n-1;i>=0;i--) #define vec(...) vector<__VA_ARGS__> #define _3cSpNGp ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; typedef long double ld; using pii=pair<int,int>; using vi=vector<int>; //snuke's mod int template <ll mod> struct modint{ ll x; // typedef long long ll; modint(ll x=0):x((x%mod+mod)%mod){} modint operator-()const{ return modint(-x);} modint& operator+=(const modint a){ if((x+=a.x)>=mod) x-=mod; return *this; } modint& operator-=(const modint a){ if((x+=mod-a.x)>=mod) x-=mod; return *this; } modint& operator*=(const modint a){ (x*=a.x)%=mod; return *this; } modint operator+(const modint a)const{ modint res(*this); return res+=a; } modint operator-(const modint a)const{ modint res(*this); return res-=a; } modint operator*(const modint a)const{ modint res(*this); return res*=a; } modint pow(ll n) const { modint res=1,x(*this); while(n){ if(n&1)res*=x; x*=x; n>>=1; } return res; } modint inv() const { return pow(mod-2); } }; using mint=modint<1000000007>; const int mxn=3000; mint fact[mxn+10]; void prefact(){ fact[0]=fact[1]=1; crep(i,2,mxn){ mint x=i; fact[i]=fact[i-1]*x; } } mint cnk(ll k,ll n){ if(k>n) return 0; mint e=fact[k]*fact[n-k]; return fact[n] * e.inv(); } int main(){ _3cSpNGp; prefact(); int n,k; cin>>n>>k; vec(string) a(n); rep(i,n){ cin>>a[i]; } std::map<string,int> mp; rep(i,n){ sort(a[i].begin(),a[i].end()); mp[a[i]]++; } vi rbts; for(auto p : mp){ rbts.pb(p.se); } n=sz(rbts); vec(mint) dp(k+1),nedp; dp[0]=1; rep(i,n){ nedp=dp; int x=rbts[i]; rep(j,k+1){ if(dp[j].x==0) continue; for(int now=1;now<=x;now++){ if(j+now*(now-1)/2>k) break; nedp[j+now*(now-1)/2]+=dp[j]*cnk(now,x); } } swap(dp,nedp); } // cout<<"\n"; cout<<dp[k].x<<"\n"; // return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...