打卡信奥刷题（3134）用C++实现信奥题 P7552 [COCI 2020/2021 #6] Anagramistica

P7552 [COCI 2020/2021 #6] Anagramistica

题目描述

Biljana 喜欢出字谜游戏。

如果一个单词可以由另一个单词交换字母顺序得到，则称它们是「相似」的。

现在，她有n nn个单词。她希望选出一些单词，使得其中恰好有k kk对单词是「相似」的。请你帮她计算可行的方案数，对10 9 + 7 10^9 + 7109+7取模。

输入格式

第一行两个整数n nn，k kk。

接下来n nn行，每行一个字符串，表示一个单词。

输出格式

一行一个整数，表示可行的方案数，对10 9 + 7 10^9 + 7109+7取模。

输入输出样例 #1

输入 #1

3 1 ovo ono voo

输出 #1

2

输入输出样例 #2

输入 #2

5 2 trava vatra vrata leo ole

输出 #2

3

输入输出样例 #3

输入 #3

6 3 mali lima imal je sve ej

输出 #3

6

说明/提示

样例 1 解释

恰含有一对「相似」的单词的方案为ovo, ono, voo和ovo, voo。

数据规模与约定

本题采用捆绑测试。

对于100 % 100\%100%的数据，1 ≤ n ≤ 2 × 10 3 1 \le n \le 2 \times 10^31≤n≤2×103，0 ≤ k ≤ 2 × 10 3 0 \le k \le 2 \times 10^30≤k≤2×103，单词的长度不超过10 1010且仅含小写字母。

说明

本题分值按 COCI 原题设置，满分110 110110。

题目译自 COCI2020-2021 CONTEST #6T3 Anagramistica。

C++实现

#include<iostream>#include<algorithm>#include<cmath>#include<unordered_map>usingnamespacestd;typedeflonglongll;constll MOD=1000000007;constintN=2e3+100;intn,k,cnt[N],id;ll dp[N][N],c[N][N];string s;unordered_map<string,int>um;intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>k;for(inti=1;i<=n;i++){cin>>s;sort(s.begin(),s.end());if(um.count(s))cnt[um[s]]++;elseum[s]=++id,cnt[id]=1;}for(inti=0;i<=n;i++){c[i][0]=1;for(intj=1;j<=i;j++)c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;}dp[0][0]=1;//初始化for(inti=1;i<=id;i++){for(intj=0;j<=k;j++){dp[i][j]=dp[i-1][j];for(into=1;o<=cnt[i]&&o*(o-1)/2<=j;o++)dp[i][j]=(dp[i][j]+dp[i-1][j-o*(o-1)/2]*c[cnt[i]][o]%MOD)%MOD;}}printf("%lld",dp[id][k]);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容