首页 > 其他分享 >数学题 2

数学题 2

时间:2024-04-20 21:45:54浏览次数:25  
标签:方案 le cdot sum Statement mathcal 数学题

T1

Statement

一个容量为 \(M(\le10000)\) 的背包。\(n(\le1000)\) 个物品,重量为 \(m_1,m_2,...,m_n\)。问在不装物品 \(i(1\le i\le n)\) 的条件下装入重量为 \(j(0\le j\le M)\) 的物品有多少种方案?对于所有的 \(i\) 和 \(j\) 作答。

Solution

\(f(i,j)\) 表示前 \(i\) 个物品,重量为 \(j\) 的方案数,\(f(0,0)=1\)

\[f(i,j)=f(i-1,j)+[j\ge m_i]\cdot f(i-1,j-m_i) \]

\(g(i,j)\) 表示不选 \(i\),重量为 \(j\) 的方案数

\[g(i,j)=f(n,j)-[j\ge m_i]\cdot g(i,j-m_i) \]

这个方程中 \(g(i,j-m_i)\) 意思是不选 \(i\) 选出 \(j-m_i\) 的方案数,等于必须选 \(i\) 选出 \(j\) 的方案数

\(\mathcal O(nm)\)

T2

Statement

求包含 \(k\) 个逆序对的长度为 \(n\) 的排列个数,\(n\le300\)。

Solution

考虑从 \(1\) 到 \(n\) 一个一个插入每个数

设插入 \(i\),则所有前 \(i-1\) 个数都比 \(i\) 小,\(i\) 可以产生 \(0\sim i-1\) 个逆序对

\(f(i,j)\) 表示前 \(i\) 个数,产生 \(j\) 个逆序对的方案数,\(f(1,0)=1\)

\[f(i,j)=\sum_{k\in[1..i]}[j-i+k\ge0]\cdot f(i-1,j-i+k) \]

转移思路:枚举 \(i\) 的插入位置,复杂度:\(\mathcal O(n^2k)\)

T3

Statement

求 \(n(n\le1000)\) 的排列个数,满足有 \(k\) 个位置 \(a_i>i\)。结果对 \(Q\) 取模。

Solution

考虑从 \(1\) 到 \(n\) 加入排列,先是加到末尾,然后可以与之前的数进行交换。

当前数为 \(i\),要交换的位置为 \(j\):

  • 若 \(a_j\le j\),则答案增加 \(1\);
  • 若 \(a_j>j\),则答案不变。

\(f(i,j)\) 表示前 \(i\) 个数,\(j\) 个位置 \(a_i>i\) 的方案数,\(f(1,0)=1\),其余初始为 \(0\)

\[f(i,j)=(j+1)\cdot f(i-1,j)+(i-j)\cdot f(i-1,j-1) \]

  • 不交换,则方案数为 \(f(i-1,j)\)
  • 与 \(a_p>p\) 交换,则方案数为 \(j\cdot f(i-1,j)\)
  • 与 \(a_p\le p\) 交换,则方案数为 \([(i-1)-(j-1)]\cdot f(i-1,j-1)=(i-j)\cdot f(i-1,j-1)\)

答案:\(f(n,k)\),复杂度:\(\mathcal O(n^2)\),注意中间要取个模

T4

Statement

给长度为 \(n(\le2\times10^5)\) 的数列 \(a\) 和 \(b(1\le a_i,b_i\le2000)\)。求

\[\sum_{i=1}^n\sum_{j=i+1}^nC_{a_i+a_j+b_i+b_j}^{a_i+a_j}\bmod(10^9+7) \]

Solution

把 \((-a_i,-b_i)\) 看成点 \(A\),\((a_j,b_j)\) 看成点 \(B\),\(C_{a_i+a_j+b_i+b_j}^{a_i+a_j}\) 即为从点 \(A\) 走到点 \(B\) 的方案数

也就是在第一、三象限都有 \(n\) 个点,坐标绝对值 \(\le2000\),求两两走到的方案数之和

考虑从一个第三象限的点 \((x,y)\) 出发走到所有第一象限的点的方案数是怎么求的:

初始 \(f(x,y)=1\),\(f(i,j)=f(i-1,j)+f(i,j-1)\)(假设可以有负数下标)

因为对于所有第三象限的点都是这么求,然后把所有第一象限的 \(f(x,y)\) 加起来,转移方程一模一样

故我们事先把所有第三象限的 \(f(x,y)\) 设为 \(1\),一遍求即可,\(\mathcal O(4000^2)\)

然后减去关于原点对称的点对的方案数再除以 2 即为答案

T5

Statement

给 \(n(n\le2000)\) 个平面整点 \((x_i,y_i)(0\le x_i,y_i\le10^5)\)。问从 \((0,0)\) 走到 \((X,Y)(0\le X,Y\le10^5)\) 且不经过任何一个给定点的方案数。

Solution

答案 = 总数 - 经过任意一个给定点的方案数

我们钦定一个点 \((x_i,y_i)\) 是必须第一次经过的,则路径被分成了从 \((0,0)\) 到 \((x_i,y_i)\) 和从 \((x_i,y_i)\) 到 \((X,Y)\) 两部分

由于从 \((x_i,y_i)\) 走到 \((X,Y)\) 没有任何限制,也就是随便走,故这一部分的答案为 \(\binom{X-x_i+Y-y_i}{X-x_i}\)

而第一部分恰好是个完全相同的子问题,故可以 dp 算,算完后两部分乘起来即可

形式化地:\(f(i)\) 表示考虑前 \(i\) 个点,从 \((0,0)\) 走到 \((x_i,y_i)\) 且不经过任何一个给定点的方案数,\(f(1)=\binom{x_1+y_1}{x_1}\)

\[f(i)=\binom{x_i+y_i}{x_i}-\sum_{j\in[1..i-1]}f(j)\cdot\binom{x_i-x_j+y_i-y_j}{x_i-x_j} \]

答案为 \(f(n)\),复杂度 \(\mathcal O(n^2)\)

T6

Statement

已知 \(k\) 次方和的通项公式为

\[\sum_{i=0}^ni^k=\dfrac1{k+1}\sum_{i=0}^kC_{k+1}^iB_i(n+1)^{k+1-i} \]

给出 \(B_i\) 的求解方式。

Solution

代入 \(n=0\) 得

\[\sum_{i=0}^kC_{k+1}^iB_i=0 \]

即对于 \(n>0\),有 \(\sum_{i=0}^nC_{n+1}^iB_i=0\)

而 \(B_0=1\),根据上式即可 \(\mathcal O(n^2)\) 递推

标签:方案,le,cdot,sum,Statement,mathcal,数学题
From: https://www.cnblogs.com/laijinyi/p/18148218/Maths-2

相关文章

  • [高考] 数学题的一般解题思路
    最近家里来了一位高中生,每天晩上辅导一下。虽然我不赞成现在的教育方式,但也脱不了随大流的现实。现根据这两周的教学经验总结一二,以便后续用的上!之前也经常听到有些学生说自己数学一点都不会。我觉的只要智力可以,没教不会的,要看老师及家人的本事了。如果在学校,要区分理解......
  • 《算法竞赛入门经典 第2版》 数学题目集
    例题10-1巨大的斐波那契数!(ColossalFibonacciNumbers!,UVa11582)巨大的斐波那契数!ColossalFibonacciNumbers!-洛谷例题10-2不爽的裁判(DisgruntledJudge,NWERC2008,UVa12169)不爽的裁判DisgruntledJudge-洛谷NOI数学学习相关书籍及视频等资料(不包......
  • 数学题目合集
    翻转性质:如果翻转的区间所有数对个数为偶,则整个逆序对个数奇偶性不变;否则改变。证明:首先翻转区间外的逆序对个数不会变化,翻转区间与翻转区间外的逆序对个数也不会变化。假设翻转前翻转区间内有\(cnt\)个逆序对,则翻转后有\(len\times(len-1)/2-cnt\)个逆序对,差为\(len\tim......
  • 数学题做题记录
    数学主要是计数和数论函数相关。[AGC031F]WalkonGraph题意:有一张\(n\)个点\(m\)条边的无向连通图\(G\),每条边有长度\(L_i\),有一个人在上面游走。有\(q\)组询问,每组询问给出\(s_i,t_i,r_i\),询问是否存在一条从\(s_i\)出发到\(t_i\)结束且长度为\(r_i\)的路径......
  • 几道数学题
    最近脑子炸了,过来做几道数学结论题。很好玩P3768简单的数学题题意求\[(\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\cdoti\cdotj)\bmodp\]其中,\(n\le10^{10},p\le1.1\times10^{10}\),\(p\)是质数题解遇事不决,推式子!!!注:\((i,j)=\gcd(i,j)\)。\[\begin{align}\sum_{i=1}^......
  • 一道很不错的高中数学题的题解解析
    引:上周六上午把一道高中的数学竞赛题(一道8分的填空题,原题如下图所示)当成一道大题(如上)郑重其事地和孩子以互动的方式探讨了这个题的题解分析. 这是一道出得很好的题.其题解所涉及的知识不超出高一目前所学内容,因此高一的学生也是可能做得出来的.但这题是一道很综合的题,涉......
  • 2656-纯easy数学题
    给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你需要执行以下操作 恰好 k 次,最大化你的得分:从 nums 中选择一个元素 m 。将选中的元素 m 从数组中删除。将新元素 m+1 添加到数组中。你的得分增加 m 。请你返回执行以上操作恰好 k 次后的最......
  • 做点数学题。
    \(\mathit1\)题意:给定长度为\(n\)的序列\(a\),\(m\)次询问,每次给定\(l,r\)和\(k\),求\(\sum\limits_{i=l}^ra_i\left(\begin{matrix}i-l\\k\end{matrix}\right)\)的值。\(1\len,m,\sumk\le10^5\)。模数为素数。我们先思考\(\sumk\le10^5\)这个限制。容易让人联想......
  • 数学题
    数学题笔记整理P2568GCD\[\sum\limits_{p\inprime}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd(i,j)=p\\\]\[\sum\limits_{p\inprime}\sum\limits_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{n}{p}\rfloor}\gcd(i......
  • P3708 koishi的数学题(取模转化减法)
    \(\displaystylef(x)=\sum_{i=1}^nx\bmodi\)对于一个i,枚举k对于[xk,x(k+1)),中的数,贡献的形式都为a[i]-i*k直接差分维护即可#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<map>#include<vector>#defineA......