UVALive-8079 Making a Team 排列组合公式化简
2024-08-31 08:34:47
题目链接:https://cn.vjudge.net/problem/UVALive-8079
题意
n个人组队,队伍人数小于等于n,每个队伍需要4个不同的职务的领导。
问这n个人可以组成多少队?
n<=1e7
思路
很明显,对一个i人队伍,可以组成$ \sum\binom{i}{1}^4\binom{n}{i} = \sum i^4\binom{n}{i} $种可能。
现在分析一下复杂度,对一个n来讲我们可以求逆元来求组合数,所以O(n)复杂度。
那么现在又有1000行的数据,总的复杂度远远超过了10s的时间。
又要优化了,这次看了半天没有优化思路,赛后有人讲把整个式子拆开即可,反正我是拆不开。
这次用用某同学的方法优化。
\[\begin{align*}
1+\sum_1^n \binom{n}{i}x^i&=(1+x)^n \\
(1+\sum_1^n \binom{n}{i}x^i)'&=((1+x)^n)' \\
\sum_1^n i\binom{n}{i}x^{i-1}&=n(1+x)^{n-1} \\
\sum_1^n i\binom{n}{i}x^i&=n(1+x)^{n-1}x \\
\sum_1^n i^2\binom{n}{i}x^i&=n(n-1)(1+x)^{n-2}x^2+n(1+x)^{n-1}x \\
\sum_1^n i^3\binom{n}{i}x^i&=n(n-1)(n-2)(1+x)^{n-3}x^3+2n(n-1)(1+x)^{n-2}x^2+ n(n-1)(1+x)^{n-2}x^2+n(1+x)^{n-1}x \\
\sum_1^n i^4\binom{n}{i}&=2^{n-4}(n^4+20n^3-55n^2+42n)
\end{align*}
\]
1+\sum_1^n \binom{n}{i}x^i&=(1+x)^n \\
(1+\sum_1^n \binom{n}{i}x^i)'&=((1+x)^n)' \\
\sum_1^n i\binom{n}{i}x^{i-1}&=n(1+x)^{n-1} \\
\sum_1^n i\binom{n}{i}x^i&=n(1+x)^{n-1}x \\
\sum_1^n i^2\binom{n}{i}x^i&=n(n-1)(1+x)^{n-2}x^2+n(1+x)^{n-1}x \\
\sum_1^n i^3\binom{n}{i}x^i&=n(n-1)(n-2)(1+x)^{n-3}x^3+2n(n-1)(1+x)^{n-2}x^2+ n(n-1)(1+x)^{n-2}x^2+n(1+x)^{n-1}x \\
\sum_1^n i^4\binom{n}{i}&=2^{n-4}(n^4+20n^3-55n^2+42n)
\end{align*}
\]
这个思路可以应对$ \sum f(i) \binom{n}{i} $形式的化简,其中f(i)是i的多项乘积。
提交过程
TLE |
AC
代码
#include <cstdio>
#include <cstring>
const int maxn=1e7+20;
const int mod=1e8+7;
int pow2[maxn];
void init(void){
pow2[0]=1;
for (int i=1; i<maxn; i++)
pow2[i]=(pow2[i-1]*2)%mod;
// printf("done\n");
}
long long pow(long long x, int num){
long long res=1;
for (int i=0; i<num; i++)
res=(res*x)%mod;
return res;
}
long long func(int n){
if (n==1) return 1;
if (n==2) return 18;
if (n==3) return 132;
return ((pow2[n-4]*(pow(n, 4) + 6*pow(n, 3) + 3*pow(n, 2) - 2*n )%mod)%mod+mod)%mod;
}
int main(void){
long long n;
init();
while (scanf("%lld", &n)==1 && n)
printf("%lld\n", func(n));
return 0;
}
Time | Memory | Length | Lang | Submitted |
---|---|---|---|---|
66ms | None | 682 | C++ 5.3.0 | 2018-08-24 23:14:22 |
最新文章
- 一步步学习javascript基础篇(0):开篇索引
- centos环境自动化批量安装软件脚本
- 【BZOJ】3757: 苹果树
- 学习之路三十六:SQL知识总结 - [游标||字符串分割]
- 有关git的换行符的处理问题
- C++——类和动态内存分配
- C# 平时碰见的问题【6】
- 快速备份sqlserver2005以上版本数据库的方法-摘自网络
- highcharts 多数据+切换
- iphone";此证书是由未知颁发机构签名的";的解决办法
- javaweb中去除某个get方式的参数,并且返回路径
- Unity非运行模式下实现动画播放/回退工具
- Mac 上Python多版本切换
- day4、Linux基础题目
- Python下载图片小程序
- Egret的按钮事件处理
- DNA Evolution CodeForces - 828E(树状数组)
- [Vue warn]: Attribute ";id"; is ignored on component <;div>; because the component is a fragment instanc
- springboot 表单校验
- web.xml配置详解(2)