位数问题（推公式）

思路没想到的原因

当时没有想到这样的方向，还在那里使劲找规律。以后一定要考虑多重方向。

思路

我们用$f[i][1]$来表示第$i$个数中有多少奇数个数字$3$，$f[i][0]$来表示第$i$个数中有多少偶数个数字$3$。记得初始化$f[1][1]=1$，$f[1][0]=9$。

还有，记得$\%12345$。当我们循环的$i<n$，说明我们可以把我们统计数中有多少偶数个数字$3$的数组等于$f[i-1][0]*9+f[i-1][1]$。还要把$f[i][1]$也更新了。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

int f[1010][10];

signed 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]*9+f[i-1][1]+12345)%12345;
			f[i][1]=(f[i-1][1]*9+f[i-1][0]+12345)%12345;
		}else{
			f[i][0]=(f[i-1][0]*8+f[i-1][1]+12345)%12345;
			f[i][1]=(f[i-1][1]*8+f[i-1][0]+12345)%12345;
		}
	}
	cout <<(f[n][0]+12345)%12345;
    return 0;
}

先先的生日（数学）

思路没想到的原因

用暴力解法，逐个判断其他的数是不是它的约数，这样时间复杂度是O(n^2)，只骗了$20$分。

思路

假设$a$是$b$的约数的话，那么$b$就是$a$的倍数。因此可以做这么一个处理，当判定某个数字$k$时，我们可以把这个数字的倍数$q$全部加$1$，含义是$q$的约数又多了一个。

考虑到可能会有很多$k$的值相同，所以可以利用桶的思想，把相同的一次性统计完。

约数和倍数是一对“好朋友”，当求时间复杂度过大时，可以考虑倍数的做法。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int tt=1e5+10;
int a[tt],cnt[tt],res[tt];

signed main(){
	freopen("birth.in","r",stdin);
	freopen("birth.out","w",stdout);
    int n;
    cin >>n;
    for(int i=0;i<n;i++){
    	cin >>a[i];
    	cnt[a[i]]++;
	}
	for(int i=1;i<tt;i++){
		if(cnt[i]==0) continue;
		for(int j=i;j<tt;j+=i){
			res[j]+=cnt[i];
		} 
	}
	for(int i=0;i<n;i++){
		cout <<res[a[i]]-1<<endl;
	}
    return 0;
}

小静的考验（数学）

思路没想到的原因

当时感觉太难了，所以把重心放在其他题目上面了。

思路

首先，得逆序循环来判断$a[i]$是否满足变化的条件。如果满足条件，就更新你用来存要分成几个的变量，还要记得向上取整和$*1.0$。

我们还得知道：如果你要切$10$根木棍，你会在一个木头上切几次？显然是$10-1=9$次。所以计数变量加上要分成几个的变量的时候，也要按照这个规律，要$-1$。

代码

#include <bits/stdc++.h>
using namespace std;

const int tt=2e5+10;
int a[tt];

int main(){
    freopen("xiaojing.in","r",stdin);
    freopen("xiaojing.out","w",stdout);
    int t;
    long long cnt=0,ans=0;
    cin >>t;
    while(t--){
    	int n;
    	cnt=0;
    	ans=0;
    	cin >>n;
    	for(int i=1;i<=n;i++){
    		cin >>a[i];
		}
		for(int i=n-1;i>=1;i--){
			if(a[i]>a[i+1]){
				cnt=ceil(a[i]*1.0/a[i+1]*1.0);
				a[i]=(a[i]*1.0)/cnt;
				ans=ans+cnt-1;
			}
		}
		cout <<ans<<endl;
	}
    return 0;
}

超级感染（数学）

思路没想到的原因

对快速幂的理解还不够透彻,没有想到关于快速幂的东西。

思路

排列组合题，直接套快速幂的模板，还有记得开$long$ $long$！

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod=100003;

int qmi(int a,int b,int p){
	int res=1;
	while(b){
		if(b&1) res=(res*a+p)%p;
		a=(a*a+p)%p;
		b=b>>1;
	}
	return res;
}

signed main(){
	freopen("super.in","r",stdin);
	freopen("super.out","w",stdout);
    int m,n;
    cin >>m>>n;
	int cnt=0;
	cnt=(((qmi(m,n,mod))+mod)%mod-((m*qmi(m-1,n-1,mod))+mod)%mod+mod)%mod;
	cout <<cnt;
    return 0;
}

超级GCD（数学）

待更新……

谢谢