【ACM组合数学 | 错排公式】写信

题目链接:https://ac.nowcoder.com/acm/contest/54484/B

题意很简单,但是数据范围偏大。

错排公式

首先来推导一下错排公式:

\[D(n) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}
\]

设一个函数:

\[S_i表示一个排列中p_i = i的方案数
\]

那么我们可以知道:

\[D(n) = n! - |\cup_{i=1}^{n}S_i|
\]

这个表示所有方案数减去至少有一个位置放对的方案数

现在来考虑一下如何处理后面这个并集,并集往往是不好求的,而交集会好求很多,所以在求并集的时候我们往往采取容斥原理将一个并集转换成诸多交集的加减运算

我们用一个图可以来表示当n = 3的情况:

【ACM组合数学 | 错排公式】写信

其中有:

\[|S_1 \cup S_2 \cup S_3| = |S_1| + |S_2| + |S_3| - |S_1 \cap S_2| - |S_1 \cap S_3| - |S_2 \cap S_3| + |S_1 \cap S2 \cap S_3|
\]

扩展一下就可以得到下面的柿子:

\[|\cup_{i=1}^{n}S_i| = \sum_{k=1}^{n}(-1)^k\sum_{1\leq i_1 \leq i_2 \leq ... \leq i_k \leq n}|S_{i1}\cap S_{i2} ... \cap S_{ik}|
\]

然后有:

\[\sum_{1\leq i_1 \leq i_2 \leq ... \leq i_k \leq n}|S_{i1}\cap S_{i2} ... \cap S_{ik}| = C_{n}^{k}(n-k)!
\]

这个表示啥呢,左边这个柿子的含义其实是i1 ~ ik都放对了,其他位置上无所谓的方案数,就等同于在n个位置中选择k个放对,剩下的随便放的方案数。

所以可得下面的柿子:

\[|\cup_{i=1}^{n}S_i| = \sum_{k=1}^{n}(-1)^kC_{n}^{k}(n-k)!
\]

然后化简得:

\[|\cup_{i=1}^{n}S_i| = \sum_{k=1}^{n}\frac{(-1)^k n!}{k!}
\]

然后代回到一开始的答案表达式中:

\[D(n) = n! - \sum_{k=1}^{n}\frac{(-1)^k n!}{k!}
\]

n!提出来,再化简一下得到:

\[D(n) = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}
\]

回到本题

但是有这个柿子依然不好写这题,这题如果是1e7就可以直接O(n)写了,但是这题是1e9的数据范围,可以考虑一下分段打表(一般要求函数可以递推),但是这个表达式好像不是很好打,我们来分析一下。

首先网上有一个比较有名递推式(证明略):

\[D(n) = (n-1)[D(n - 1) + D(n - 2)]
\]

这个递推需要用到前两项,也就是说我们需要打两个表,然后才可以做,有点麻烦,但是其实是可以只用一项的。

我看网路上都没有用下面这种方式递推的,我在这里写一下。

我们考虑D(n) -> D(n + 1)这样的转移:

\[D(n) = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!}
\]

\[D(n + 1) = (n + 1)! \sum_{k=0}^{n + 1}\frac{(-1)^k}{k!}
\newline = (n + 1)![\sum_{k=0}^{n}\frac{(-1)^k}{k!} + \frac{(-1)^{n + 1}}{(n + 1)!}]
\newline = (n + 1)!\sum_{k=0}^{n}\frac{(-1)^k}{k!} + (-1)^{n + 1}
\newline = (n + 1) \times n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} + (-1)^{n + 1}
\newline = (n+1) \times D(n) + (-1)^{n+1}\]

然后令段大小T = 1e7打表打出D(0), D(T), D(2T) ... D(100T)就好了。

最终的复杂度是O(n)但是常数极小,所以可以过。

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int p = 1e9 + 7, T = 1e7;

int a[110] =
{
1,824182295,933713113,474482547,930651136,251064654,637937211,229643390,307311871,448853213,
322273426,398890147,194914852,884947442,154199209,881788023,389699639,733217502,601739182,
372305477,213823357,713959988,498202615,196342945,324300550,154001751,974475946,540773759,
467881322,257531902,598680559,367927849,971346692,94577421,617165552,128327758,503709458,
253566817,820144401,13965056,82358069,805941568,533047638,69430220,686678173,297170813,
34546238,323435423,499126069,487532712,468899710,790590914,581347156,955359050,700529992,
518280890,98592091,64544225,988209678,422603955,40661679,174468756,573631136,757555557,
710709955,775098981,499158883,969149294,880429710,42564126,333697951,522067888,579797877,
528967798,717694718,309384913,31308092,316850320,220854491,878646494,963974981,377654637,
705101053,542246848,466289530,750036412,819636314,688721174,464087273,517164631,256789690,
482685016,276682441,473333947,340221393,762927538,624766601,984537252,977632075,34192646,
402182971,977005016
};

int mo(int x){return (x % p + p) % p;}

void solve()
{
	int n;cin >> n;
	int ans = a[n / T];
	for(int i = n / T * T + 1;i <= n; ++ i)ans = mo(ans * i % p + ((i & 1) ? -1 : 1));
	cout << ans << '\n';
}


void table()
{
	int x = 1;//d(0) = 1,这个有点特殊
    cout << x << ",";
    int cnt = 1;
    for(int i = 1;i <= 1e9; ++ i)
    {
        x = x * i % p;
        if(i & 1)x = (x - 1 + p) % p;
        else x = (x + 1) % p;
        
        if(i % T == 0)
        {
        	cout << x << ",";
    		cnt ++;
    	}
    	
        if(cnt % 10 == 0)
        {
        	cout << '\n';
        	cnt = 1;
        }
        
    }
}

signed main()
{
    table();
	solve();
	//return 0;
}

原文链接:https://www.cnblogs.com/eriktse/p/17325308.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:【ACM组合数学 | 错排公式】写信 - Python技术站

(0)
上一篇 2023年5月19日
下一篇 2023年4月17日

相关文章

  • 手把手教你python实现SVM算法

    手把手教你Python实现SVM算法 支持向量机(Support Vector Machine,SVM)是一种经典的分类算法,它通过寻找最优超平面来实现分类。在本攻略中,我们将介绍如使用Python实现SVM算法,并提供两个示例来说明如何使用SVM算法进行分类。 步骤1:了解SVM算法 在SVM算法中,我们需要考虑以下因素: 超平面:SVM通过寻找最优超平面…

    python 2023年5月14日
    00
  • 京东LBS推荐算法实践

    作者:京东零售 郑书剑 1、推荐LBS业务介绍 1.1 业务场景 现有的同城购业务围绕京东即时零售能力搭建了到店、到家两种业务场景。同城业务与现有业务进行互补,利用高频,时效性快的特点,可以有效提升主站复访复购频次,是零售的重要战略方向。 1.2 名词解释 LBS:基于位置的服务(Location Based Services)。 下文LBS商品代指京东小时…

    算法与数据结构 2023年4月17日
    00
  • 带你了解Java数据结构和算法之递归

    带你了解Java数据结构和算法之递归 什么是递归? 递归是一种算法或计算机程序的设计方法,在程序执行过程中直接或间接的调用自身。 递归的实现方式 递归的实现通常使用函数进行的。在函数中,我们首先检查停止条件(递归基)是否满足,如果满足,我们停止递归;否则,我们调用自身递归进行下一步计算。 递归的应用场景 递归通常在解决问题中使用。对于像树、图等复杂结构的遍历…

    数据结构 2023年5月17日
    00
  • 朴素贝叶斯算法的python实现方法

    朴素贝叶斯算法的Python实现方法 朴素贝叶斯算法是一种基于贝叶斯定理的分类算法,它的基本思想是通过计算先验概率和条件概率来确定一个样本属于某个类的概率,从而实现分类。在Python中,可以使用多种库来实现朴素贝叶斯算法,包括scikit-learn、nltk等。本文将详细讲解朴素贝叶斯算法的Python实现方法,包括算法原理、Python实现过程和示例。…

    python 2023年5月13日
    00
  • 教你如何用python开发一款数字推盘小游戏

    以下是关于“教你如何用Python开发一款数字推盘小游戏”的完整攻略: 简介 数字推盘是一款简单的益智游戏,玩家需要将数字方块推到指定位置,以达到游戏目标。在本教程中,我们将介绍如何使用Python开发一款数字推盘小游戏,并使用示例说明如何实现游戏逻辑和界面设计。 游戏规则 数字推盘游戏的规则如下: 游戏区域为一个$N\times M$的网格,其中包含若干数…

    python 2023年5月14日
    00
  • Java 超详细图解集合框架的数据结构

    下面是完整攻略: Java 超详细图解集合框架的数据结构 简介 集合框架是Java中最基础的数据结构之一,是大部分Java程序员必须掌握的基础知识。这个框架提供了常用的数据结构和算法,包括List、Set、Map等等。本文将带领您从数据结构的角度详细解析Java集合框架中的各种数据结构,让您能够清晰地掌握它们的特点和使用方法。 数据结构 Java集合框架中的…

    数据结构 2023年5月17日
    00
  • python之基数排序的实现

    Python实现基数排序算法 基数排序算法是一种非比较排序算法,它的基本思是将待排序的元素按照位数切割成不同的数字,然后按每个位数分别进行排序。具体步骤如下: 找出待排序数组中最大的数字,并确定其位数。 从最低位开始,按照每个位数进行排序。具体做法是,将待排序数组中的数字按照当前位数的值进行分组,然后按照每个组的顺序重新排列数组。 重复上述操作,直到将所有的…

    python 2023年5月14日
    00
  • Python数据拟合与广义线性回归算法学习

    Python数据拟合与广义线性回归算法学习 数据拟合和广义线性回归是机器学习中常用的技术,用于建立数据模型并预测结果。本文将详细讲解Python实现数据拟合和广义线性回归算法的整个攻略,包括算法原理、实现过程和示例。 算法原理 数据拟合 数据拟合是一种用于建立数据模型的技术,基本思想是通过拟合已有数据来预测未来的结果。在Python中,可以使用numpy和s…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部