DAY13

T1位数问题（题目传送门）

思路

找规律 f[i][0]代表i位数中偶数个3的个数，f[i][1]代表i位数中奇数个3的个数。 $f[i][0]=f[i-1][0]*9+f[i-1][1]$ 是因为 在第i-1位数前可以接0，1，2，4，5，6，7，8，9这样是偶数个3.原来的偶数个3还是偶数个3 在第i-1位前接一个3 可以让之前奇数个3变成偶数个3 $f[i][1]=f[i-1][0]+f[i-1][1]*9$ 是因为 在第i-1位数前可以接0，1，2，4，5，6，7，8，9这样是奇数个3.原来的奇数个3还是奇数个3 在第i-1位前接一个3 可以让之前偶数个3变成奇数个3

注意 当i==n时 因为最高位不能是0所以只能*8

代码

#include<bits/stdc++.h>
using namespace std;
long long f[1010][2];
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]*9+f[i-1][1])%12345;
			f[i][1]=(f[i-1][0]+f[i-1][1]*9)%12345;
		}
		else f[i][0]=(f[i-1][0]*8+f[i-1][1])%12345;
	}
	cout<<f[n][0]%12345;
 	return 0; 
}

🙂思路没想到的原因

思路想错了😐

T2先先的生日（题目传送门）

思路

因为枚举约数会超时，所以我们枚举倍数。用一个桶数组，将所有纸条的数存起来。如果cnt[i]有，我们将他的倍数都加上cnt[i]。 时间复杂度$O(nlog_en)$是不会超时的

最后答案还要-1因为会把自己算上

代码

#include<bits/stdc++.h>
using namespace std;
int a[100010],cnt[100010],res[100010];
int main()
{
	//freopen("bit.in","r",stdin);
	//freopen("bit.in","r",stdout);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		cnt[a[i]]++; 
	}
	for(int i=1;i<=n;i++)
	{
		if(cnt[i]==0) continue;
		for(int j=i;j<=n;j+=i)
		{
			res[j]+=cnt[i];
		}
	}
	for(int i=1;i<=n;i++) cout<<res[a[i]]-1<<endl;
}

思路没想到的原因

没有用逆向思维，没有想到用倍数

T3小静的考验（题目传送门）

T4 超级感染（题目传送门）