草庐IT

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

Eriktse Runtime 2023-07-20 原文

题目链接：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的情况：

其中有：

\[|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;
}
写信ACMsectioncodestrong算法与数据结构

有关【ACM组合数学 | 错排公式】写信的更多相关文章

  1. ruby - 最多 n 的组合 - 2

    给定一个数组a，什么是实现其组合直到第n的最佳方法？例如:a=%i[abc]n=2#Expected=>[[],[:a],[:b],[:c],[:a,b],[:b,:c],[:c,:a]] 最佳答案 做如下:a=%w[abc]n=30.upto(n).flat_map{|i|a.combination(i).to_a}#=>[[],["a"],["b"],["c"],["a","b"],#["a","c"],["b","c"],["a","b","c"]] 关于ruby-最多n的组合，我

  2. ruby - Rails 组合多个 activerecord 关系 - 2

    我想合并多个事件记录关系例如，apple_companies=Company.where("namelike?","%apple%")banana_companies=Company.where("namelike?","%banana%")我想结合这两个关系。不是合并，合并是apple_companies.merge(banana_companies)=>Company.where("namelike?andnamelike?","%apple%","%banana%")我要Company.where("名字像？还是名字像？","%apple%","%banana%")之后，我会写代

  3. ruby - 如何在 ruby 中组合/排列？ - 2

    我有一个熟悉的问题，看起来像是数学世界的排列/组合。如何通过ruby​​实现以下目标？badges="1-2-3"badge_cascade=[]badges.split("-").eachdo|b|badge_cascade["1","2","3"]ButIwantittobeis:=>["1","2","3","1-2","2-3","3-1","2-1","3-2","1-3","1-2-3","2-3-1","3-1-2"] 最佳答案 函数式方法:bs="1-2-3".split("-")strings=1.upto(bs.

  4. ruby - 我可以在 Ruby 中动态调用数学运算符吗？ - 2

    ruby中有这样的东西吗？send(+,1,2)我想让这段代码看起来不那么冗余ifop=="+"returnarg1+arg2elsifop=="-"returnarg1-arg2elsifop=="*"returnarg1*arg2elsifop=="/"returnarg1/arg2 最佳答案 是的，只需像这样使用send(或者更好的是public_send):arg1.public_send(op,arg2)这是可行的，因为Ruby中的大多数运算符(包括+、-、*、/、andmore)只需调用方法。所以1+2与1.+(2)相同

  5. ruby - 更快的 n 选择 k 来组合数组 ruby - 2

    在尝试解决“网格上的路径”问题时，我编写了代码defpaths(n,k)p=(1..n+k).to_ap.combination(n).to_a.sizeend代码工作正常，例如ifn==8andk==2代码返回45，这是正确的路径数。但是，当使用较大的数字时，代码非常慢，我正在努力想出如何加快这个过程。 最佳答案 与其构建组合数组只是为了计算它，不如编写function定义组合的数量。我敢肯定还有包含此功能和许多其他组合函数的gem。请注意，我使用的是gemDistribution对于Math.factorial方法，但这是另一种

  6. ruby-on-rails - Ruby 哈希组合 - 2

    对于一个电子商务应用程序，我试图将选项的散列(每个选项都有一系列选择)转换为代表这些选择组合的散列数组。例如:#Input:{:color=>["blue","grey"],:size=>["s","m","l"]}#Output:[{:color=>"blue",:size=>"s"},{:color=>"blue",:size=>"m"},{:color=>"blue",:size=>"m"},{:color=>"grey",:size=>"s"},{:color=>"grey",:size=>"m"},{:color=>"grey",:size=>"m"}]Input内部可能有额

  7. ruby - 为什么 Ruby 的 splat 在组合数组时比使用 + 组合数组慢？ - 2

    我大胆猜测将一个数组拼成另一个数组比将两个数组加在一起更快，但经过快速基准测试后我发现我错了。我假设解释器只会将splat转换为数组文字，而不必每次都对其调用+方法。那么，为什么+比splat更快？我使用了这个基准代码:deftest(trials=1000)head=[1,2,3]tail=100.times.to_at=Time.now.to_ftrials.timesdo|i|a=[head,*tail]endputs"splatdonein#{Time.now.to_f-t}"t=Time.now.to_ftrials.timesdo|i|a=head+tailendputs"

  8. ruby |设计数学？ - 2

    情况:我正在编写一个程序来求解素数。我需要解决4x^2+y^2=n的问题，其中n是一个已知变量。是的，必须是Ruby。我愿意在这个项目上花费大量时间。我最好自己编写方程式的求解算法，并将其作为该项目的一部分。我真正喜欢的是:如果任何人都可以向我提供指南、网站的链接，或者关于与求解代数方程特别相关的形式算法的构造的歧义消除，或者向我提供似乎你是读者它会帮助我完成任务。请不要建议我使用其他语言。如果您在回答之前接受我真的非常想这样做，我将不胜感激。该项目没有范围或时间限制，也不以营利为目的。这是为了我自己的教育。注意:我并不直接反对为Ruby实现和使用现存的数学库/模块/其他东西，但我更喜

  9. ruby - 我在哪里可以找到 Ruby 中的数学密集型应用程序 - 2

    我发现许多Rails应用程序主要针对企业、社交网络类型的Web应用程序。我看到有人将Ruby与一些出色的OOPS语言(如Java和C#)进行了比较，但我确实发现很难获得一些数学密集型应用程序。非常感谢任何知识渊博的输入(指向示例程序的链接等)，其中轻松显示了语言的用法，就像快速启动或显示该语言如何用于各种数学问题一样。 最佳答案 不幸的是，Ruby并没有在数学和科学计算领域涉足太多。目前，有一个名为SciRuby的pre-alpha库它试图为Ruby带来更多面向数学的功能。他们正试图构建一个NumPy/SciPy等价物。SciRub

  10. ruby - Ruby 的排序方法如何与组合比较(宇宙飞船)运算符一起工作？ - 2

    这里是初级程序员，只是想了解Ruby背后的过程sort使用飞船操作符时的方法.希望有人能帮忙。在以下内容中:array=[1,2,3]array.sort{|a,b|ab}...我明白sort一次比较一对数字，然后返回-1如果a属于b之前,0如果它们相等，或者1如果a应该遵循b.但是在降序排序的情况下，像这样:array.sort{|a,b|ba}...到底发生了什么？是否sort还是比较ab然后翻转结果？或者它是在解释return的-1,0和1具有相反的行为？换句话说，为什么要像这样将变量放在block中:array.sort{|b,a|ba}...结果与第一个示例中的排序模式相同？

随机推荐