제출 #1331823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1331823		ahmetlbktd4	Anagramistica (COCI21_anagramistica)	C++20	0 / 110	7 ms	15940 KiB

anagramistica

#include "bits/stdc++.h"
#define ff first
#define ss second
#define ll long long
using namespace std;

const int N = 2e3+3;
const int mod = 1e9+7;

ll f[N],in[N];
int dp[N][N];
vector <int> a;

ll pw(int a,int b){
    if (!b)
    return 1;
    ll h = pw(a,b/2);
    if (b&1)
    h = (h*a)%mod;
    return (h*h)%mod;
}

ll C(int n,int k){
    return f[n] * in[k]%mod * in[n-k]%mod;
}

int coz(int m,int k){
    int &h = dp[m][k];
    if (~h)
    return h;
    if (!m && !k)
    return h = 1;
    h = 0;
    for (int i = 0;i <= a[m-1];i++){
        if (i*(i-1)/2 > k)
        break;
        h = (h+(C(a[m-1],i)*coz(m-1,k-i*(i-1)/2))%mod)%mod;
    } 
    return h;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0;i <= N;i++){
        fill(dp[i],dp[i]+N,-1);
    }
    f[0] = 1;
    for (int i = 1;i < N;i++){
        f[i] = (f[i-1]*i)%mod;
    }
    in[N-1] = pw(f[N-1],mod-2);
    for (int i = N-2;i >= 0;i--){
        in[i] = (in[i+1]*(i+1))%mod;
    }
    int n,k;
    cin >> n >> k;
    map <string,int> mp; 
    for (int i = 0;i < n;i++){
        string s;
        cin >> s;
        sort(s.begin(),s.end());
        mp[s]++;
    }
    int m = 0;
    for (auto i : mp){
        a.push_back(i.ss);
        m++;
    }
    // dp[0][0] = 1;
    // for (int i = 1;i <= m;i++){
    //     for (int j = 0;j <= k;j++){
    //         for (int h = 0;h <= a[i-1];h++){
    //             if (h*(h-1)/2 > j)
    //             break;
    //             dp[i][j] = (dp[i][j] + C(a[i-1],h)*dp[i-1][j-h*(h-1)/2])%mod;
    //         }
    //     }
    // }
    cout << coz(m,k) << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from anagramistica.cpp:1:
In function 'constexpr typename __gnu_cxx::__enable_if<std::__is_scalar<_Tp>::__value, void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]',
    inlined from 'constexpr void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = int*; _Tp = int]' at /usr/include/c++/13/bits/stl_algobase.h:977:21,
    inlined from 'constexpr void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]' at /usr/include/c++/13/bits/stl_algobase.h:1007:20,
    inlined from 'int main()' at anagramistica.cpp:46:13:
/usr/include/c++/13/bits/stl_algobase.h:931:18: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 16056048 bytes into a region of size 16048036 overflows the destination [-Wstringop-overflow=]
  931 |         *__first = __tmp;
      |         ~~~~~~~~~^~~~~~~
anagramistica.cpp: In function 'int main()':
anagramistica.cpp:11:5: note: destination object 'dp' of size 16048036
   11 | int dp[N][N];
      |     ^~

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