Submission #887182

#	Time	Username	Problem	Language	Result	Execution time	Memory
887182		kbtdauma	Anagramistica (COCI21_anagramistica)	C++14	10 / 110	13 ms	14424 KiB

anagramistica

#include <bits/stdc++.h>                    /// D__P
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll mod = 1e9+7;
const int hh = 2005;
const int hd = 1e6+5;
#define OK signed main()
#define happy ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define I_love_Hoang_Diep(filename) freopen(filename".inp","r",stdin); freopen(filename".out","w",stdout);
#define TIME (1.0*clock()/CLOCKS_PER_SEC)
#define for0(i,n) for(ll i=0;i<n;i++)
#define foru(i,a,b) for(int i=a;i<=b;i++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define all(s) (s).begin(),(s).end()
#define sz(a) (a).size()
#define ms(f,v) memset((f),v,sizeof(f))
#define gcd __gcd
#define lcm(a,b) (a*b)/gcd(a,b)
#define vll vector<ll>
#define vi vector<int>
#define pf push_front
#define pb push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define mp make_pair
#define fi first
#define se second
#define bit(i,j) ((i>>j)&1)
using namespace std;
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l,ll r)
{
    return l+(rd()*1LL*rd()%(r-l+1)+(r-l+1))%(r-l+1);
}
int n,k,b[hh]; string a[hh];
void nhap()
{
    cin>>n>>k;
    foru(i,1,n) cin>>a[i], sort(all(a[i]));
    sort(a+1,a+n+1); int sl=0, id=-1;
    //foru(i,1,n) cout<<a[i]<<'\n';
    foru(i,1,n)
    {
        if(a[i]!=a[i-1]) b[++id]=sl, sl=1;
        else sl++;
    }
    b[++id]=sl; n=id;
    //foru(i,1,n) cout<<b[i]<<' ';
}
int add(int x,int y)
{
    if((x+=y)>=mod) x-=mod;
    return x;
}
int mul(int a,int b)
{
    a%=mod, b%=mod;
    return (a*b)%mod;
}
int f[hh][hh],ans,C[hh][hh];
void build()
{
    foru(i,0,2000)
    {
        C[0][i]=1;
        foru(j,1,i) C[j][i]=add(C[j][i-1],C[j-1][i-1]);
    }
    // foru(i,0,n)
    // {
    //     foru(j,0,n) cout<<C[i][j]<<' '; 
    //     cout<<'\n';
    // }
}
void solve()
{
    f[0][0]=1;
    sort(b+1,b+n+1);
    //foru(i,1,n) cout<<b[i]<<' ';
    foru(i,1,n)
    {
        foru(j,0,k)
        {
            foru(t,0,b[i])
            {
                int w=C[2][t];
                if(j-w>=0) f[i][j]=add(mul(C[t][b[i]],f[i-1][j-w]),f[i][j]);
            }
        }
    }
    cout<<f[n][k];
}
OK
{
    happy; //I_love_Hoang_Diep("cuteevcl");
    nhap(); build(); solve();
    cerr<<"\nTime elapsed: "<<TIME<<"s\n";
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 70