BZOJ3823 定情信物

2014.12.27 10:50 Sat| 6 visits oi_2015| 2015_刷题日常| Text

Solution

很不幸,这道题的出题人在心满意足地出完这套题后不小心发现它竟然可以组合数取模完虐正解,于是正解就便变成了组合数取模……

不知道为什么,Hint变成了对于样例2的解释【郁闷】。还有这个题真是水啊,,刚刚半天就有19个AC了……不过被zky大神说成是一道有点意思的题,貌似还是蛮开心?

30分算法

令 $E_{m,n}$ 表示 $n$ 维超立方体表面上 $m$ 维超立方体(0≤m≤n)的个数。由“ $n$ 维超立方体可看作由 $n-1$ 维超立方体沿垂直于它的所有的棱的方向平移得到的立体图形”,可以得到:

在此基础上写暴力递推求解,便可得到30分。真是水得令人无法直视。

70分算法

由上述递推式可得到 $E_{m,n}=2^{n-m}\times{n!\over m!(n-m)!}$ (当然,这一公式也可根据超立方体的几何性质直接得到。详情可见OEIS)。

于是,直接利用Exgcd和快速幂求组合数取模即可。

100分算法

可以很直接地想到先线性预处理出关于模P的乘法逆元,之后 $\mathcal O(n)$ 递推求组合数取模就可以拿到满分。

另外,题目中的异或只是因为出题人的本意是输出所有元素种类的个数,但因输出文件过大,不得已才改为了输出答案间的异或和,同时也欢迎利用异或的性质AC此题的解法(如果存在的话)。

蒟蒻后来被大神D了……囧

现在的题目允许n%p==0……于是……

Code

数据加强前

#include <bits/stdc++.h>
using namespace std;
#define N 10000005
int n,p,inv[N];
int main()
{
    cin>>n>>p;
    inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=(long long)(p-p/i)*inv[p%i]%p;
    int t=1,ans=1;
    for(int i=n-1;i>=0;i--)
        ans^=(t=(long long)t*inv[n-i]%p*2*(i+1)%p);
    cout<<ans<<endl;
    return 0;
}

数据加强后

Rank1的代码是怎么写的?

别傻了,我怎么可能告诉你萌~

出题人的愤怒:怒刷rank前三 -_-||