#乘法逆元,组合计数#洛谷 1313 codevs 1137 jzoj 3027 计算系数

2024-02-11 06:18

本文主要是介绍#乘法逆元,组合计数#洛谷 1313 codevs 1137 jzoj 3027 计算系数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

给定一个多项式$ (ax + by)^k$ ,请求出多项式展开后 $xnym $项的系数。


分析

根据二项式定理,有 ( a x + b y ) k = ∑ i = 0 k C k i a i b k − i x i y k − i (ax+by)^k=\sum_{i=0}^kC_k^ia^ib^{k-i}x^iy^{k-i} (ax+by)k=i=0kCkiaibkixiyki,所以 x n y m x^ny^m xnym项的系数为 C k a n b m C_ka^nb^m Ckanbm,然后通过快速幂和乘法逆元求出答案。


代码

#include <cstdio>
#define mod 10007
using namespace std;
typedef long long ll;
ll a,b,k,n,m,ans;
ll ksm(ll x,ll y){ll ans=1;while (y){if (y&1) ans=ans*x%mod;x=x*x%mod; y>>=1;}return ans;
}
ll c(ll n,ll m){ll ans=1;for (ll i=n-m+1;i<=n;i++) ans=ans*i%mod;for (ll i=1;i<=m;i++) ans=ans*ksm(i,mod-2)%mod;return ans;
}
int main(){scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m);ans=ksm(a,n)*ksm(b,m)%mod*c(k,n)%mod;return !printf("%lld",ans);
}

这篇关于#乘法逆元,组合计数#洛谷 1313 codevs 1137 jzoj 3027 计算系数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/699044

相关文章

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

如何用Java结合经纬度位置计算目标点的日出日落时间详解

《如何用Java结合经纬度位置计算目标点的日出日落时间详解》这篇文章主详细讲解了如何基于目标点的经纬度计算日出日落时间,提供了在线API和Java库两种计算方法,并通过实际案例展示了其应用,需要的朋友... 目录前言一、应用示例1、天安门升旗时间2、湖南省日出日落信息二、Java日出日落计算1、在线API2

hdu4828(卡特兰数+逆元)

这题的前几个数据分别为1,2,5,14,32......................然后确定这是个卡特兰数列 下面来介绍下卡特兰数,它的递推式为f[i+1] = f[i]*(4*n - 6)/n,其中f[2] = f[3] =1;f[4] = 2;f[5] = 14;f[6] = 32.................................. 但是这题的n太大了,所以要用到逆元,

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

poj 1113 凸包+简单几何计算

题意: 给N个平面上的点,现在要在离点外L米处建城墙,使得城墙把所有点都包含进去且城墙的长度最短。 解析: 韬哥出的某次训练赛上A出的第一道计算几何,算是大水题吧。 用convexhull算法把凸包求出来,然后加加减减就A了。 计算见下图: 好久没玩画图了啊好开心。 代码: #include <iostream>#include <cstdio>#inclu

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

XTU 1237 计算几何

题面: Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn