题目连接:uva 766 - Sum of powers
题目大意:将Sk(n)=∑i=1nik化简成Sk(n)=ak+1nk+1+aknk+⋯+a0M
解题思路:
已知幂k,并且有(n+1)k=C(kk)nk+C(k−1k)nk−1+⋯+C(0k)n0结论。
所以令 (n+1)k+1−nk+1=C(kk+1)nk+C(k−1k+1)nk−1+⋯+C(0k+1)n0
nk+1−(n−1)k+1=C(kk+1)(n−1)k+C(k−1k+1)(n−1)k−1+⋯+C(0k+1)(n−1)0
…
2k+1−1k+1=C(kk+1)1k+C(k−1k+1)1k−1+⋯+C(0k+1)10
将各项累加起来的(n+1)k−1=C(kk+1)Sk(n)+C(k−1k+1)Sk−1(n)+⋯+C(0k+1)S0(n)
#include <cstdio>
#include <cstring>
typedef long long ll;
const int N = 25;
ll m[N], a[N][N];
ll C[N][N];
ll gcd (ll a, ll b) {
return b == 0 ? a : gcd(b, a%b);
}
inline ll cal (ll d) {
if (d < 0)
return -d;
return d;
}
inline ll sign (ll d) {
if (d > 0)
return 1;
else if (d < 0)
return -1;
else
return 0;
}
void del (ll& t, ll* p, int n) {
ll d = gcd(t, p[0]);
for (int i = 1; i <= n; i++) {
if (p[i] == 0)
continue;
d = gcd(d, cal(p[i]));
}
t /= d;
for (int i = 0; i <= n; i++)
p[i] = cal(p[i]) / d * sign(p[i]);
}
void add (ll* p, ll* q, ll k, ll& t, ll f, int n) {
for (int i = 0; i <= n; i++)
p[i] = p[i] * f - q[i] * k * t;
t *= f;
del(t, p, n);
}
void init () {
C[0][0] = 1;
for (int i = 1; i < N; i++) {
C[0][i] = C[i][i] = 1;
for (int j = 1; j < i; j++)
C[j][i] = C[j-1][i-1] + C[j][i-1];
}
memset(a, 0, sizeof(a));
m[0] = 1;
a[0][1] = 1;
for (int i = 1; i <= 20; i++) {
int u = i+1;
for (int j = 1; j <= u; j++)
a[i][j] += C[j][u];
m[i] = 1;
for (int j = 0; j < i; j++) {
add (a[i], a[j], C[j][u], m[i], m[j], u);
}
m[i] *= C[i][u];
del(m[i], a[i], u);
}
}
int main () {
init();
int cas, k;
scanf("%d", &cas);
while (cas--) {
scanf("%d", &k);
printf("%lld", m[k]);
for (int i = k+1; i >= 0; i--)
printf(" %lld", a[k][i]);
printf("\n");
if (cas)
printf("\n");
}
return 0;
}
分享到:
相关推荐
Leetcode-Problem-1780__检查数字是否为三的幂之和__Python3 描述 给定一个整数n ,如果可以将n表示为三的幂的和,则返回... -Get the ternary representation of the given number _n_ -Check if there is _2_ in th
AXP221s 是一款高度集成的电源系统管理芯片,针对单芯锂电池 ( 锂离子或锂聚合物 ) 且需要多路电源转换输出的应用,提供简单易用而又可以灵活配置的完整电源解决方案,充分满足多核应用处理器系统对于电源相对复杂而...
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
杰基尔初学者 使用和Jekyll 站点的。 入门 您需要安装 、 和 。 然后安装构建依赖项 npm install 提示:请务必提交生成的package-lock.json和Gemfile.lock文件。 然后构建和服务开发站点,运行 ...
discover-superpowers-game, 3D 个超级游戏platforming演示使用 Cannon.js 发现超强的演示在你的浏览器中播放演示。下载源项目并将它的解压缩到你的服务器文件夹( 服务器文件夹)的 。获得超级并制作你自己的HTML5...
superpowers-xregexp-plugin Superpowers 的 XRegXExp 插件,可扩展的 HTML5 2D+3D 游戏引擎。 XRegExp 是一个开源(MIT 许可)JavaScript 库,提供增强和可扩展的正则表达式。 您将获得浏览器本身不支持的新语法...
MathPlus 插件 用于数学函数的 Superpowers 插件。
KW 12库尔斯布拉特的Kurs beispiele zu Den PowerDays: ://ppedv.de/schulung/kurse/WindowsPowerShellCorecmdletScriptWMIlernenFortgeschrittenWorkflowProgrammierungSeminarTraining.aspx
数学手册--积分--序列。 Contents Preface to the Seventh Edition xxi ...0.12 Sums of powers of natural numbers ........................ 1 0.13 Sums of reciprocals of natural numbers ..................
matlab代码粒子群算法PSO的审查 我的论文《粒子群优化算法...Sum of Different Power 其他 涉及算法的代码可以在以下位置找到: 我还在文章中发布了关于志虎SPSO(标准粒子群优化)的介绍,该文章可以在以下位置找到:
参考文献:KOOPMAN R,POWERS W,WANG Z,et al.Give credit where credit is due:tracing value added in global production chains[R].NBER working paper,No.312011,2011. 全球价值链参与度GVCpt=GVCpt_f+GVCpt_b ...
适用于Superpowers的桌面应用程序 ---
赋予您的应用程序自动部署超级能力在这个项目中,您将证明您对以下学习目标的精通: 解释CI / CD的基础知识和收益,以实现,构建和部署基于云的软件产品的自动化。 利用部署策略来设计和构建支持持续交付流程的CI / ...
赋予您的应用程序自动部署超级能力在这个项目中,您将证明您对以下学习目标的精通: 解释CI / CD的基础知识和收益,以实现,构建和部署基于云的软件产品的自动化。 利用部署策略来设计和构建支持持续交付流程的CI / ...
Superpowers是可。 您可以像普通的脱机游戏制作者一样单独使用它,也可以设置密码,让朋友们通过其Web浏览器加入您的项目。 这对于长时间合作,在一个周末干扰或仅在调试中互相帮助非常有用!...不只是为了制作游戏...
Superpowers 验证器插件,可扩展的 HTML5 2D+3D 游戏引擎。 字符串验证器和消毒器库。 文档 像往常一样使用验证器: validator . equals ( "abc" , "Abc" ) ; validator . contains ( "foo" , "foobar" ) ; ...
superpowers-asset-packs, 你的游戏的CC0许可资产包 Superpowers资产包 在 itch.io 下载资产包 。这个存储库中的资产是由像素男孩在Sparklin实验室创建的。它们是在 Creative Commons零( CC0 ) 许可下发布的。他们的...
2021全球零售力量(英)Global Powers of Retailing 2021.pdf