文章
260
标签
8
分类
82
首页
时间轴
标籤
分类
组织
REZICS(轮回社)
荒原研究所
更新Blog
友链
关于
世界尽头のWasteland
数
返回首页
搜索
首页
时间轴
标籤
分类
组织
REZICS(轮回社)
荒原研究所
更新Blog
友链
关于
数
发表于
2022-10-14
|
更新于
2026-02-11
|
Algorithm
Data-structure
|
浏览量:
文章作者:
边缘坐标
文章链接:
https://blog.rezedge.com/posts/9579b8d3/
版权声明:
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议。转载请注明来源
世界尽头のWasteland
！
上一篇
洛谷-P1590 失踪的7
link 废话不多说，直接思路+题解。。。 思路具体思路是计算出每一个数对总方案数的贡献方法数，然后求和就好了。比如n=4321：1 的贡献值：很明显是1，只能有1这一种可能性。2 的贡献值：注意在十位，所以贡献值应该是 $2∗9^1$3 的贡献值：在百位，应该是 $3∗9^2$4 的贡献值：在千位，应该是 $49^3$所以某一个数的设位数为b，值为a贡献值就是 $a9^{b-1}$然而，如何去证明呢？很简单，因为7不可用，每一位自然有9个选择那么根据乘法原理，一位数随机排列为9种，两位数为81种，n位数就是 $9n9^n$9n 种，也就是 说，0-99999....9就可以用乘法原理来算，如果去掉0这种情况，再加上100000......0这 种情况，一加一减抵消了，总数没有变。就变成了1-100000......0的总数为 $a*9^b$种。 至此，我们就证明完了贡献值公式是正确的，但是，为什么总数是这些贡献值加起来呢？我们用位置原理 就能证明。还是之前那个例子，n=4321，计算出了4的贡献值，相当于我们已经算完了1......4000了，剩下无论如何千位数也不会...
下一篇
AcWing 271. 杨老师的照相排列
AcWing 271. 杨老师的照相排列前言相关分析时间复杂度由均值不等式，最坏情况下共有 (Nk)k(Nk)k 状态，计算每个状态需要 O(k)O(k) 的计算量，因此总时间复杂度是 O(k(Nk)k)O(k(Nk)k)。https://www.acwing.com/solution/content/4954/ 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <iostream>#include <algorithm>#include <cstring>using namespace std;const int N = 31;int k = 1;long long dp[N][N][N][N][N];int main(){ while (cin >> k, k) { int n[6] = {0}; for (int i...
评论
边缘坐标
文章
260
标签
8
分类
82
Follow Me
公告
行走于世界的边缘，荒原的拾荒人。
最新文章
虚拟机连入错误
2026-02-11
重置网络堆栈
2026-02-11
Cursor如何安装离线插件
2026-02-11
JSX 嵌套注释问题
2026-02-11
zx
2026-02-11
搜索
数据加载中
