P7552 [COCI 2020/2021 #6] Anagramistica题目描述Biljana 喜欢出字谜游戏。如果一个单词可以由另一个单词交换字母顺序得到则称它们是「相似」的。现在她有n nn个单词。她希望选出一些单词使得其中恰好有k kk对单词是「相似」的。请你帮她计算可行的方案数对10 9 7 10^9 71097取模。输入格式第一行两个整数n nnk kk。接下来n nn行每行一个字符串表示一个单词。输出格式一行一个整数表示可行的方案数对10 9 7 10^9 71097取模。输入输出样例 #1输入 #13 1 ovo ono voo输出 #12输入输出样例 #2输入 #25 2 trava vatra vrata leo ole输出 #23输入输出样例 #3输入 #36 3 mali lima imal je sve ej输出 #36说明/提示样例 1 解释恰含有一对「相似」的单词的方案为ovo, ono, voo和ovo, voo。数据规模与约定本题采用捆绑测试。Subtask分值数据规模与约定1 1110 10101 ≤ n ≤ 15 1 \le n \le 151≤n≤152 2230 30300 ≤ k ≤ 3 0 \le k \le 30≤k≤33 3370 7070无附加约定对于100 % 100\%100%的数据1 ≤ n ≤ 2 × 10 3 1 \le n \le 2 \times 10^31≤n≤2×1030 ≤ 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实现#includeiostream#includealgorithm#includecmath#includeunordered_mapusingnamespacestd;typedeflonglongll;constll MOD1000000007;constintN2e3100;intn,k,cnt[N],id;ll dp[N][N],c[N][N];string s;unordered_mapstring,intum;intmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinnk;for(inti1;in;i){cins;sort(s.begin(),s.end());if(um.count(s))cnt[um[s]];elseum[s]id,cnt[id]1;}for(inti0;in;i){c[i][0]1;for(intj1;ji;j)c[i][j](c[i-1][j]c[i-1][j-1])%MOD;}dp[0][0]1;//初始化for(inti1;iid;i){for(intj0;jk;j){dp[i][j]dp[i-1][j];for(into1;ocnt[i]o*(o-1)/2j;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考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容