解题报告：luogu P2220

指挥使走后一脸懵逼，然后想起了一道水\(SB\)的省选题。

这是毒瘤乘法分配率的应用，似乎还有一篇，算是入门题。

对了，这题连接：P2220 [HAOI2012]容易题

然而蒟蒻还是先自闭了一会......

大力代值可知，是一道裸的条件概率。

先处理出\(sum=\sum_{i=1}^{n}\)与\(sum^n\)(这是用分配率推导的，我这里不用了，就是无限制条件下的最大值)，在处理每个被影响的区块就好了，就是乘上

\[\dfrac{{sum-\sum_{i=\text{被限制的数}}i}}{sum}
\]

这里被限制的数只有\(k\in[1,1e5]\)个，暴力一下即可，注意要排序和去重!!

那么这样的复杂度就是\(O(k\log k)\)的，可以通过本题。

我下面说个问题，其实此题已解决了，不过......

显然要求出\(sum\)在模\(1e9+7\)意义下的逆元，那么这个数一定存在吗？

即求：

\[(1e9+7)k=\dfrac{n(n+1)}{2}\;\;\;k\in Z
\]

是否在数据范围内存在正整数解\(k\)。

显然\(1e9+7\)是质数，那么\(n\)和\(n+1\)一个中显然有因子\(1e9+7\)，而且另一个数是偶数，那么易得\(n_{min}=1e9+7>1e9\)，是没问题的。

下面上代码了：

\(Code\):

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int MAXN=100005;

const int MOD=1000000007;

typedef long long ll;

inline long long mul(long long x,long long y,long long mod)

{

	long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);

	return tmp<0 ? tmp+mod : tmp;

}//数据不小，加上保险

struct node

{

	ll id,val;

}a[MAXN],b[MAXN];

bool cmp(node n,node m){if(n.id^m.id) return n.id<m.id;else return n.val<m.val;}

ll n,m,k,cnt=0;

ll sum,inv,s;

ll quickpow(ll a,ll b)

{

	ll base=a%MOD,ans=1;

	while(b)

	{

		if(b&1) ans=mul(ans,base,MOD);

		b>>=1;

		base=mul(base,base,MOD);

	}

	return ans%MOD;

}

ll get_inv(ll x){return quickpow(x,1000000005)%MOD;}

void hack()//真坑~去重

{

	for(int i=1;i<=k;i++)

	{

		if(a[i].id==b[cnt].id&&a[i].val==b[cnt].val) continue;

		else b[++cnt]=a[i];

	}

}

void work()

{

	sum=n*(n+1)/2;

	sort(a+1,a+k+1,cmp);

	hack();

	inv=get_inv(sum)%MOD;

	s=quickpow(sum,m);

	int l=0;

	ll now=sum;

	for(int i=1;i<=cnt;i++)

	{

		if(b[i].id==b[l].id) now-=b[i].val;

		else

		{

			s=mul(s,mul(inv,now,MOD),MOD)%MOD;

			now=sum-b[i].val;

			l=i;

		}

	}

	s=mul(s,mul(inv,now,MOD),MOD)%MOD;//最后还剩下一组

	return;

}

int main()

{

	scanf("%lld%lld%lld",&n,&m,&k);

	//正确思路挂成70pts，原因：

	//n,m还要是long long否则后边求sum时得到的还是int

	for(int i=1;i<=k;i++) scanf("%lld%lld",&a[i].id,&a[i].val);

	work();

	cout<<s%MOD<<"\n";

	return 0;

}

巴特西

解题报告：luogu P2220

\(Code\):

最新文章

热门文章