oj.uz

Submission #887183

# Submission time Handle Problem Language Result Execution time Memory
887183 2023-12-14T01:52:56 Z kbtdauma Anagramistica (COCI21_anagramistica) C++14
110 / 110
 23 ms 29012 KB 
#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);
}
ll 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); ll 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]<<' ';
}
ll add(ll x,ll y)
{
    if((x+=y)>=mod) x-=mod;
    return x;
}
ll mul(ll a,ll b)
{
    a%=mod, b%=mod;
    return (a*b)%mod;
}
ll 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])
            {
                ll 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])%mod;
            }
        }
    }
    cout<<f[n][k]%mod;
}
OK
{
    happy; //I_love_Hoang_Diep("cuteevcl");
    nhap(); build(); solve();
    cerr<<"\nTime elapsed: "<<TIME<<"s\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23132 KB Output is correct
2 Correct 17 ms 23132 KB Output is correct
3 Correct 17 ms 23132 KB Output is correct
4 Correct 17 ms 23132 KB Output is correct
5 Correct 17 ms 23132 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23380 KB Output is correct
2 Correct 18 ms 24412 KB Output is correct
3 Correct 18 ms 23388 KB Output is correct
4 Correct 19 ms 24504 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23132 KB Output is correct
2 Correct 17 ms 23132 KB Output is correct
3 Correct 17 ms 23132 KB Output is correct
4 Correct 17 ms 23132 KB Output is correct
5 Correct 17 ms 23132 KB Output is correct
6 Correct 20 ms 23380 KB Output is correct
7 Correct 18 ms 24412 KB Output is correct
8 Correct 18 ms 23388 KB Output is correct
9 Correct 19 ms 24504 KB Output is correct
10 Correct 19 ms 24972 KB Output is correct
11 Correct 18 ms 23132 KB Output is correct
12 Correct 18 ms 23388 KB Output is correct
13 Correct 18 ms 23384 KB Output is correct
14 Correct 18 ms 23900 KB Output is correct
15 Correct 19 ms 23388 KB Output is correct
16 Correct 23 ms 29012 KB Output is correct
17 Correct 22 ms 23384 KB Output is correct
18 Correct 18 ms 24136 KB Output is correct