位数问题

思路

1. 用f1来表示积数个3的数量
2. 用f0来表示偶数个3的个数

思路：

1. 我们在做题时，发现如果是偶数个3时，只要加上一个不是3的个数，就还是。而是奇数个时，只要加上1个三就可以了
2. 如果是奇数个3时，只要加上一个不是3的个数，就还是。而是偶数个时，只要加上1个三就可以了

代码

#include<bits/stdc++.h>
using namespace std;
long long f[1010][2];
const long long MOD=12345;
int main(){
	freopen("bit.in","r",stdin);
	freopen("bit.out","w",stdout);
	int n;
	cin>>n;
	f[1][0]=9;
	f[1][1]=1;
	for(int i=2;i<=n;i++){
		if(i==n){
			f[i][0]=(f[i-1][0]*8+f[i-1][1])%MOD;
		}else{
			f[i][0]=(f[i-1][0]*9+f[i-1][1])%MOD;
			f[i][1]=(f[i-1][1]*9+f[i-1][0])%MOD;
		}
	}
	cout<<f[n][0];
	return 0;
}

反思

我当时理解错了题意，认为是因数，以后定当手动模拟样例。

这一次我还知道，当不是DP却像DP时，也可以优化空间，只要思考用了多少数组就好了。

如果只用了前一位，就可以优化！

先帝的生日

思路

求约数时间复杂度较多，所以我们可以枚举倍数：每个数的倍数

代码

#include<bits/stdc++.h>
using namespace std;
long long a[100010];
unordered_map<int,int> mp,res;
int main(){
	freopen("birth.in","r",stdin);
	freopen("birth.out","w",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mp[a[i]]++;
	}
	for(int i=1;i<=1000000;i++){
		if(mp[i]==0) continue;
	//	cout<<"i:"<<i<<" 个数："<<mp[i]<<endl;
		for(int j=i;j<=1000000;j+=i){
			res[j]+=mp[i];
		}
	}
	for(int i=1;i<=n;i++){
		cout<<res[a[i]]-1<<endl;
	}
	return 0;
}

反思

我知道了约数与倍数不仅是“仇敌”，还是可以一起奋战的战友，当约数时间复杂度超标时，还可以用逆向找倍数。

超级感染

思路

本题是快速幂，整体的样数减去不满足条件的就是了。

经过推理不能完成感染的总数为m乘以m-1的n-1次方。

代码

#include<bits/stdc++.h>
using namespace std;
const long long MOD=100003;
long long ans(long long a,long long b,long long p){
	long long res=1;
	while(b){
		if(b&1){
			res=(a*res+p)%p;
		}
		a=(a*a)%p;
		b/=2;
	}
	return res;
}
int main(){
	freopen("super.in","r",stdin);
	freopen("super.out","w",stdout);
	long long n,m;
	cin>>m>>n;
	long long res=(ans(m,n,MOD)+MOD)%MOD-(m*ans(m-1,n-1,MOD)+MOD)%MOD;
	cout<<(res+MOD)%MOD;
	return 0;
}