思路
看到「恰好」触发被动了
考虑套路转化, 令 \(f(k)\) 表示「至少」有 \(k\) 个对应位置的字符不同的字符串对数
套路的, 令 \(g(k)\) 表示「恰好」有 \(k\) 个对应位置的字符不同的字符串对数
\[f(k) = \sum_{i = k}^{n} {n \choose i} g(i) \iff g(k) = \sum_{i = k}^{n} (-1)^{i - k} {n \choose i} f(i) \]考虑 \(f\) 怎么算, 你发现不好算, 是有点零帧起手了, 好好想一下
正难则反, 转化成「钦定」\(k\) 个位置相同, 然后丢进去简单转化
你容易发现, 令 \(f(n - k)\) 表示「至少」有 \(n - k\) 个位置对应的字符相同, 即「至多」有 \(k\) 个位置不同
还是带进套路里面计算, 令 \(f(k)\) 表示「至多」有 \(k\) 个位置不同
\[f(k) = \sum_{i = 0}^{k} {n - i \choose n - x}g(i) \iff g(k) = \sum_{i = 0}^{k} (-1)^{x - i} {n - i \choose n - x} f(i) \]根据上面的变换, \(f(k)\) 如何计算?
你容易发现, 二进制枚举「钦定」相同的 \(n - k\) 个位置, 然后剩下的只需要暴力统计即可, 一共只有 \(36^4\) 种情况
结束了
总结
新 \(\rm{trick}\) , 之前看到过所以能独立做出来, 加油, 继续努力!
「钦定」意义下「至多」和「恰好」的转化, 简化问题的计算
很裸的题, 正难则反
每次推组合数学的柿子怎么都是错的, 不要想当然啊
标签：至多,pin,套路,CEOI2010,sum,位置,day2,choose,钦定 From： https://www.cnblogs.com/YzaCsp/p/18644692