每日归档： 2018年12月31日

不知不觉就到了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;
}