首页 > 其他分享 >[COCI2020-2021#6] Anagramistica

[COCI2020-2021#6] Anagramistica

时间:2024-09-11 22:06:13浏览次数:13  
标签:facinv COCI2020 Anagramistica int res 2021 字符串 dp mod

[COCI2020-2021#6] Anagramistica

题意

给定 \(n\) 个字符串和正整数 \(k\)。

定义两个字符串相似当且仅当两个字符串排序后相等。

可以从中选出一些字符串,求有多少种方案,使得其中恰好有 \(k\) 对字符串相似。

思路

先将所有字符串排序,相同的归为一类,求出 \(cnt_i\) 表示第 \(i\) 种字符串的个数。

定义 \(dp_{i,j}\) 表示前 \(i\) 种字符串,有 \(j\) 对相似的方案数。

转移方程:\(dp_{i,j} = \sum dp_{i-1,j-C_k^{2}}\times C_{cnt_i}^{k}\)。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 5;
const int mod = 1e9 + 7;
int n, k, dp[N][N], fac[N], facinv[N];
map <string, int> M;
int qpow(int a, int b) {
	int res = 1;
	for (; b; b >>= 1, a = a * a % mod) 
		if (b & 1) res = res * a % mod;
	return res;
}
int C(int x, int y) {
	return fac[x] * facinv[y] % mod * facinv[x - y] % mod;
}
void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; i ++) {
		string s; cin >> s;
		sort(s.begin(), s.end());
		M[s] ++;
	}
	fac[0] = facinv[0] = 1;
	for (int i = 1; i <= 2000; i ++) {
		fac[i] = fac[i - 1] * i % mod;
		facinv[i] = qpow(fac[i], mod - 2);
	}
	dp[0][0] = 1; int l = 0;
	for (auto p : M) {
		l ++;
		for (int i = 0; i <= k; i ++)
			for (int j = 0; j <= p.second; j ++) {
				if (i < j * (j - 1) / 2) continue;
				dp[l][i] += dp[l - 1][i - j * (j - 1) / 2] * C(p.second, j);
				dp[l][i] %= mod;
			}
	}
	cout << dp[l][k] << "\n"; 
}
signed main() {
	int Case = 1;
//	cin >> Case;
	while (Case --)
		solve();
	return 0;
}

标签:facinv,COCI2020,Anagramistica,int,res,2021,字符串,dp,mod
From: https://www.cnblogs.com/maniubi/p/18409062

相关文章

  • [NOIP2021] 方差
    链接鉴于\(luogu\)经常似,这里把\(Markdown\)粘过来了题目[NOIP2021]方差题目描述给定长度为\(n\)的非严格递增正整数数列\(1\lea_1\lea_2\le\cdots\lea_n\)。每次可以进行的操作是:任意选择一个正整数\(1<i<n\),将\(a_i\)变为\(a_{i-1}+a_{i+1}......
  • [COCI2020-2021#4] Vepar
    [COCI2020-2021#4]Vepar题意给定两组正整数\(a,a+1,\ldots,b\)和\(c,c+1,\ldots,d\)。判断\(c\times(c+1)\times\ldots\timesd\)能否被\(a\times(a+1)\times\ldots\timesb\)整除。思路将\(c\times(c+1)\times\ldots\timesd\)转化为\(\frac{d!}{(c-1)!}......
  • [COCI2020-2021#3] Vlak
    [COCI2020-2021#3]Vlak题意Nina和Emilija在玩游戏。Nina先手,两人轮流在纸上写下一个字母。每个玩家写下字母后得到的单词必须是该玩家喜欢的歌曲中某个单词的前缀。不能操作的玩家输,判断最后谁会赢。思路对每个玩家喜欢的歌曲建立字典树。搜索每个玩家的操作,每次在两......
  • [COCI2020-2021#5] Po
    [COCI2020-2021#5]Po题意给出一个序列\(a\),有一个序列\(b\),初始全为\(0\)。可以对序列\(b\)进行如下操作:使一个连续的区间内的所有数加上一个正整数\(x\)。但要求任意两个操作区间要么互不相交,要么一个包含另外一个。求将序列\(b\)变为序列\(a\)的最小操作次数。......
  • [COCI2021-2022#6] Zemljište
    [COCI2021-2022#6]Zemljište题意给出一个矩阵,一个子矩阵的权值为\(|m-a|+|m-b|\),\(m\)为子矩阵数值和,\(a,b\)为给出的数。求该矩阵权值最小的子矩阵。思路枚举子矩阵上界和下界,左右界使用双指针枚举,令\(a<b\)。对于每个左界,不断扩展右界直到子矩阵和大于\(b\),因为再......
  • 「NOI2021 D1T3 庆典」题解
    uoj675加强:\(\sumk\le6\times10^5\)暴力\(u\)在\(s\Rightarrowt\)路径上\(\iff\)正图上\(s\Rightarrowu\)且反图上\(u\Rightarrowt\)时间复杂度\(O((n+m)q)\)正解只关心可达性,不妨SCC缩点成DAG。注意到一个奇怪的条件:对于三座城市\(x,y,z\),若\(x\Right......
  • Mynavi Programming Contest 2021 (AtCoder Beginner Contest 201) A~E 题解
    A-TinyArithmeticSequence题目大意给定序列\(A=(A_1,A_2,A_3)\)。能否将\(A\)重新排列,使得\(A_3-A_2=A_2-A_1\)?\(1\leA_i\le100\)输入格式\(A_1~A_2~A_3\)输出格式如果能将\(A\)重新排列使得\(A_3-A_2=A_2-A_1\),输出Yes;如果不能,输出No。样例\(A\)输出\((5......
  • AISing Programming Contest 2021 (AtCoder Beginner Contest 202) A~E 题解
    A-ThreeDice一个人抛了三个骰子,它们的顶面分别是\(a,b,c\)。求它们的底面之和。这里用的骰子是标准骰子,即两个相对的面之和为\(7\)。\(1\lea,b,c\le6\)输入格式\(a~b~c\)输出格式输出答案。样例\(a\)\(b\)\(c\)答案\(1\)\(4\)\(3\)\(13\)\(5\)\(6......
  • KYOCERA Programming Contest 2021 (AtCoder Beginner Contest 200) A~E 题解
    A-Century题目大意公元\(N\)年在第几个世纪中?一个世纪是由\(100\)个年份组成的一个区间。如,\(1\)世纪为\([1,100]\)年,\(2\)世纪为\([101,200]\)年,……\(1\leN\le3000\)输入格式\(N\)输出格式将答案输出为一个整数。样例\(N\)输出\(2021\)\(21\)\(200......
  • 计算机考研真题知识点——2021(A)
    目录2021(A)一、选择题二、判断题三、简答题四、综合题2021(A)一、选择题1、C语言程序是从程序中的main函数开始执行的。2、 intx=2,y=3,z=4; x<z?y:z //的结果是?34、若说明语句“inta[5],*p=a;”,则对数组元素的正确引用是()A、a[p]B、p[a]C、*(p+2)D、p+......