lp5431 【模板】乘法逆元2


挺套路的。
先计算出所有数的积的逆元,再计算除了这个数以外的数的积,然后乘一起,这样就完成了线性求逆元。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
const int N=5000005;
inline int rd(){
	int rt=0;char ch=getchar();
	while(!isdigit(ch)){ch=getchar();}
	while(isdigit(ch)){rt=rt*10+ch-'0';ch=getchar();}
	return rt;
}
int n,MOD,k;
int a[N],pr[N],sf[N];
inline int pw(int A,int X){
	int RT=1;
	while(X){
		if(X&1){
			RT=1ll*RT*A%MOD;
		}
		A=1ll*A*A%MOD;X>>=1;
	}
	return RT;
}

void init(){
	scanf("%d%d%d",&n,&MOD,&k);
	int pl=1;
	pr[0]=sf[n+1]=1;
	for(int i=1;i<=n;++i){
		a[i]=rd();
	}
	for(int i=1;i<=n;++i){
		pr[i]=1ll*pr[i-1]*a[i]%MOD;
	}
	pl=pw(pr[n],MOD-2);
	for(int i=n;i>=1;--i){
		sf[i]=1ll*sf[i+1]*a[i]%MOD;
	}
	int nk=1;
	int ans=0;
	for(int i=1;i<=n;++i){
		nk=1ll*nk*k%MOD;
		ans+=1ll*(1ll*pr[i-1]*sf[i+1]%MOD)*(1ll*pl*nk%MOD)%MOD;ans%=MOD;
	}
	printf("%d\n",ans);
	
}
int main(){
	init();
	return 0;
}

CF1091 Good Bye 2018

不知不觉就到了2018的最后一天。这个博客也有两个多月了。
我的姿势水平固然有了一定长进,但和巨神的距离却是越拉越远了。
这场CF也是,手速场我却没能有足够的手速。尤其是D题那种超简单的题目却死磕了半天才磕出来,F也没做出来。
总之,祝大家新年快乐_(:з」∠)_


CF1091A
依题意即可。
千万别掉进分类讨论的坑里。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int a,b,c;

void init(){
	scanf("%d%d%d",&a,&b,&c);
	--b,c-=2;
	printf("%d",min(min(a,b),c)*3+3);
}
int main(){
	init();
	return 0;
}

CF1091B
我们将每个宝藏都加上每一个向量箭头,并标记目的地。
答案是任意一个被标记n次的。
可以用map或者hashmap维护。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
int a[1005],b[1005],c[1005],d[1005];
typedef pair<int,int> pii;
typedef map<pii,int> mppii;
mppii mp;
int n;
void init(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d%d",a+i,b+i);
	}
	for(int i=1;i<=n;++i){
		scanf("%d%d",c+i,d+i);
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			pii nw(a[i]+c[j],b[i]+d[j]);
			++mp[nw];
		}
	}
	mppii::iterator it=mp.begin();
	while(it!=mp.end()){
		if(it->second==n){
			printf("%d %d\n",it->first.first,it->first.second);
			break;
		}
		++it;
	} 
}
int main(){
	init();
	return 0;
}

CF1091C
观察题意以后我们发现,对于\(k\),当且仅当\(n\%k == 0\)的时候,\(k\)会和其他的本质不同。
依据剩余系的性质容易证明。
那么我们就得到了一个朴素的求答案公式:
$$\forall x,st:n\% x==0,ans_{x}=\sum_{i=0}^{n/gcd(n,x)-1}(1+(ix-1)\%n+1) $$
然后考虑到\(n\%x==0\),所以
$$ans_{x}=\sum_{i=0}^{n/gcd(n,x)-1}(1+(ix-1)\%n)==\sum_{i=0}^{n/gcd(n,x)-1}(1+ix)$$
套上等差数列求和公式即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline long long gcd(long long A,long long B){
	return B?gcd(B,A%B):A;
}
long long n;
long long ans[100005],tp=0;

inline void calc(int X){
	long long tms=n/gcd(n,X);
	ans[++tp]=tms+((((tms*(tms-1))>>1)*X));
}

void init(){
	scanf("%I64d",&n);
	for(int i=1;i*i<=n;++i){
		if(!(n%i)){
			calc(i);
			if(i*i!=n){
				calc(n/i);
			}
		}
	}
	sort(ans+1,ans+1+tp);
	tp=unique(ans+1,ans+1+tp)-1-ans;
	for(int i=1;i<=tp;++i){
		printf("%I64d ",ans[i]);
	}
}
int main(){
	init();
	return 0;
}

CF1091D
由于长度为\(n\),显然序列的值必然是\(\frac{(n*(n+1))}{2}-SUM_i+SUM_{i+1}\), 其中\(SUM_{i}\)表示第\(i\)个排列的某个前缀和。
又排列的性质我们会发现,对于任意两个相邻的全排列,它的任意长度前缀和要么增加且前缀序列变化,要么前缀和保持不变且前缀序列保持不变。
故而,如果一个序列要满足要求,它只有两种情况——它本身就是一个排列,或者它横跨的两个排列必然有一部分前缀相同。
对于第一种情况我们可以看成它们的前缀有\(0\)个相同的。
问题转化为了,求所有排列中,两种相邻排列前缀相同的长度的和。
通过打表找规律,或者对全排列性质的精确推演,我们得到了这样一个求和式:
$$ ans=\sum_{pre=0}^{n-2}(n!-(\Pi_{i=n}^{n-pre+1}i))$$
但是暴力计算的复杂度最坏是\(n^2\)的,仍然无法通过此题。
我们考虑优化这个求和。优化的点在于\(\Pi_{i=n}^{n-pre+1}i\),我们(毫不)惊讶地发现,它等价于\(\frac{n!}{n-pre}\),所以我们可以预处理阶乘和阶乘的逆元。
这样就做完了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const long long MOD=998244353;

long long fac[1000005],inv[1000005];
long long n;

void init(){
	scanf("%I64d",&n);
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=n;++i){
		fac[i]=fac[i-1]*i%MOD;
		inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
	}
	for(int i=2;i<=n;++i){
		inv[i]=inv[i-1]*inv[i]%MOD;
	}
	long long ans=fac[n];
	for(int i=1;i<=n-2;++i){
		ans+=(fac[n]-fac[n]*inv[n-i]%MOD+MOD)%MOD;
		ans%=MOD;
	}
	printf("%I64d",ans);
}
int main(){
	init();
	return 0;
}

lp5104 红包发红包

在\(\lbrack 0,1 \rbrack \)中任取一个数,期望是\(\frac{1}{2}\)
同理,在\(\lbrack 0,w \rbrack \)中任取一个数,期望是\(\frac{w}{2}\)
故而,取\(k\)个数的期望是\(\frac{w}{2^k}\)
费马小定理加快速幂即可。

#include<iostream>
#include<cstdio>
const long long MOD = 1000000007;

inline long long pw(int A,long long X){
	long long RT=1,BS=A;
	while(X){
		if(X&1){
			RT*=BS;
			RT%=MOD;
		}
		BS*=BS;
		BS%=MOD;
		X>>=1;
	}
	return RT;
}

inline long long inv(int X){
	return pw(X,MOD-2);
}

long long w,n,k;

void init(){
	scanf("%lld%lld%lld",&w,&n,&k);
	printf("%lld\n",(w*(inv(pw(2,k))))%MOD);
}

int main(){
	init();
	return 0;
}

lp2260 清华集训2012 模积和

题目大意:求式子:
$$\sum_{i=1}^{n}\sum_{j=1}^{m}(n\ mod\ i)*(m\ mod\ j) (i \ne j)$$
的值。

那么容斥以后等价于求:
$$\sum_{i=1}^{n}\sum_{j=1}^{m}(n\ mod\ i)*(m\ mod\ j)-\sum_{i=1}^{min(n,m)}(n\ mod\ i)*(m\ mod\ i)$$

首先求:
$$\sum_{i=1}^{n}\sum_{j=1}^{m}(n\ mod\ i)*(m\ mod\ j)$$

首先,我们有定理:
$$ n\ mod\ p=n-p*\lfloor \frac{n}{p} \rfloor$$
然后配合上\(\Sigma\)的运算法则,我们可以把原式转化为:
$$n^{2}*m^{2}-m^{2}\sum_{i=1}^{n}i\lfloor \frac{n}{i} \rfloor-n^{2}\sum_{j=1}^{m}j\lfloor \frac{m}{j} \rfloor-\sum_{i=1}^{n}i\lfloor \frac{n}{i} \rfloor \sum_{j=1}^{m}j\lfloor \frac{m}{j} \rfloor$$
我们设:
$$ P=\sum_{i=1}^{n}i\lfloor \frac{n}{i} \rfloor,Q=\sum_{j=1}^{m}j\lfloor \frac{m}{j} \rfloor$$
所以我们可以用数论分块来分别计算\(P,Q\)的值。

而,对于第二部分:
$$R=\sum_{i=1}^{min(n,m)}(n\ mod\ i)*(m\ mod\ i)$$
我们不妨令\(n<m\)
那么将原式展开,可得:
$$R=\sum_{i=1}^{n}n*m-n*i\lfloor \frac{m}{i} \rfloor-m*i\lfloor \frac{n}{i} \rfloor+i^{2}\lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor$$
这个式子显然也是可以数论分块的。但是我们需要计算\(i^{2}\)对于式子的贡献。
用一些简单的证明方法可以得到:
$$\sum_{i=1}^{n}i^{2}=\frac{n(2n+1)(n+1)}{6}$$
那么它的区间和即是:
$$\sum_{i=1}^{r}i^{2}-\sum_{i=1}^{l-1}i^{2}=\frac{(2r^2+2rl+2l^2-r-3l+2)(r-l+1)}{6}$$
于是我们就可以统计整个结果了。

现在我们来考虑数论分块。

数论分块是一种处理形如
$$ \sum_{i=1}^{n}\lfloor \frac{n}{i} \rfloor$$
的公式的求值的方法。

而对于函数:

$$f(x)=\lfloor \frac{a}{x} \rfloor$$

可以发现,对于连续的一段\(x\)的区间,它的值是相同的。
具体来说是,令值为\(k\)则,令区间的左端点为\(l\),则整个区间的值为:
$$k=\lfloor \frac{n}{l} \rfloor$$
那么右端点\(r\)很显然是满足方程:
$$\lfloor \frac{n}{x} \rfloor=k$$
的最大值。
依据整除的性质得到的引理一,我们发现:
$$r=\lfloor \frac{n}{k} \rfloor$$
从而,区间为:
$$[l,\lfloor \frac{n}{\lfloor \frac{n}{l} \rfloor} \rfloor$$

附:对于引理一的证明:

引理一:求证方程:
$$\lfloor \frac{n}{x} \rfloor=k$$
的解的最大值\(t\)为
$$t=\lfloor \frac{n}{k} \rfloor$$
我们令方程的一个合法解\(x\)满足:
$$x*k+r=n\ (0\le r < x)\ (1)$$
并令:
$$t=x+d$$
那么,有:
$$\lfloor \frac{n}{x+d} \rfloor=k$$
则:
$$(x+d)*k+r’=n\ (0\le r < x+d)\ (2)$$
联立方程\((1),(2)\)可得:
$$d*k+r’=r$$
由整除的定义可得:
$$d=\lfloor \frac{r}{k} \rfloor$$
很显然,当
$$x=\lfloor \frac{n}{k} \rfloor$$
时,
$$r=n\ mod\ k,r<k,\lfloor \frac{r}{k} \rfloor=0$$
此时\(x\)取到最大值。
证毕。

另:尽量用模块化编程,而不是去化简式子。这样可以用复杂度换取正确率。

#include<iostream>
#include<cstdio>
const long long MOD = 19940417;
const long long inv2 = 9970209;
const long long inv6 = 3323403;
long long n,m;
inline long long sm1(long long A){
    return (A*(A+1)%MOD)*inv2%MOD;
}
inline long long sm2(long long A){
    return ((A*(A+1)%MOD)*(2*A+1)%MOD)*inv6%MOD;
}
void init(){
    scanf("%lld%lld",&n,&m);
    n>m?n^=m^=n^=m:0; 
    long long P,Q,R;
    int l,r;
    r=0,P=0;
    while(r<n){
        l=r+1;
        r=(n/l)?(n/(n/l)):n;
        P+=(((r-l+1)*(n/l)%MOD)*(l+r)%MOD*inv2)%MOD;
        P%=MOD;
//        printf("P:%lld\n",P);
    }
    P%=MOD;
    r=0,Q=0;
    while(r<m){
        l=r+1;
        r=(m/l)?(m/(m/l)):m;
        Q+=(((r-l+1)*(m/l)%MOD)*(l+r)%MOD*inv2)%MOD;
        Q%=MOD;
//        printf("Q:%lld\n",Q);
    }
//    printf("%lld %lld\n",P,Q);
    Q%=MOD;
    R=(n*m%MOD)*n%MOD;
    long long ans=(n*m%MOD)*(n*m%MOD)%MOD-(n*n%MOD)*Q%MOD-(m*m%MOD)*P%MOD+P*Q%MOD;
    ans%=MOD;
    ans+=MOD;
    ans%=MOD;
    r=0;
    while(r<n){
        l=r+1;
        r=std::min((n/l)?(n/(n/l)):n,(m/l)?(m/(m/l)):m);
        CNT1=m/l;
        CNT2=n/l;
        R-=((((sm1(r)-sm1(l-1))%MOD)*(m/l)%MOD)*n%MOD+(((sm1(r)-sm1(l-1))%MOD)*(n/l)%MOD)*m%MOD);
        R+=(((sm2(r)-sm2(l-1))%MOD)*((m/l)*(n/l)%MOD))%MOD;
        R%=MOD;
    }
    ans-=R;
    ans%=MOD;
    ans+=MOD;
    ans%=MOD;
    printf("%lld",ans);
    
}
int main(){
    init();
    return 0;
}