|
1月26日 |
||
|
时间段 |
记录 |
备注 |
|
8:00---8:30 |
请假
|
|
|
8:30---9:00 |
|
|
|
9:00----9:30 |
|
|
|
9:30---10:00 |
|
|
|
10:00—10:30 |
|
|
|
10:30---11:00 |
|
|
|
11:00---11:30 |
|
|
|
11:30---13:30 |
午休 |
|
|
13:30---14:00 |
看书+3道小例题 |
|
|
14:00—14:30 |
|
|
|
14:30—15:00 |
|
|
|
15:00—15:30 |
费解的开关 |
|
|
15:30---16:00 |
|
|
|
16:00---16:30 |
|
|
|
16:30---17:00 |
汉诺塔问题 |
|
|
17:00---18:30 |
|
|
|
18:30—21:30 |
汉诺塔问题 |
|
|
Sumdiv（分治） |
|
|
|
|
||
|
整理今日 |
|
|
分享交流：
（待书写）
附：可以贴各种资料或题解
费解的开关
若固定了第一行，则若改变第i行某位数字，若i-1行已经固定，则只能点击i+1行的该位置上的数字才可以。
递归妙！！！！真的妙。
汉诺塔问题
1、汉诺塔三塔问题 d[n]=2*d[n-1]+1
2、汉诺塔四塔问题 f[n]=min{x*f[i]+d[n-i]}
3、汉诺塔m盘n塔问题。f[i][j]=minf[k][j]∗2+f[i−k][j−1]。设f[i][j]为有i个盘子j个柱子时的最少步数. 那么肯定是把一些上面盘子移动到某根不是j的柱子上, 然后把剩下的盘子移动到j, 然后再把上面的盘子移动到j. 于是就有递推式f[i][j]=min{f[k][j]∗2+f[i−k][j−1],f[i][j]}
Sumdiv
求A^B的所有约数之和mod 9901
1、（看到满串公式就脑壳疼）理解不了为啥用乘法分配律就可以从约数集合得到那个式子，后来在onglu大佬的帮助之下成功理解（在线%神仙）。
2、后面那个分治法求sum真的是妙啊，等比数列这么一提，妙，真的妙。经过二分再配合快速幂，时间复杂度瞬间下降（书上是O(logc),然鹅我不会算（雾，妙啊）。
3、然后我就卡死在实现上了qaq。
4、分解质因数竟然不会写了，素数筛也忘了（我可能是个废人）晚上重学素数筛。
5、想得脑壳疼。最终在某位大佬的某篇博客的帮助下，写出来了（不容易啊qaq）
6、数学真妙啊！
我jio的很有必要贴一下我的AC代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+3;
const int mod=9901;
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int A,B,cnt,prime[maxn];
long long factor[100][2];//0存因子，1存次方.
void getprime( );//素数筛
int getfactors(long long x);//分解质因数
long long ksm(long long a,long long b);//快速幂
long long sum(long long p,long long n);//核心公式
int main(){
int A,B;
A=read();
B=read();
getprime();
long long ans=1;
getfactors(A);
for(int i=0;i<cnt;i++){
ans*=(sum(factor[i][0],B*factor[i][1])%mod);
ans%=mod;
}
printf("%d",ans);
return 0;
}
void getprime( ){
memset(prime,0,sizeof(prime));
for(int i=2;i<=maxn;i++){
if(!prime[i])
prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&prime[j]<maxn/i;j++){
prime[prime[j]*i]=1;
if(i%prime[j]==0)
break;
}
}
}
int getfactors(long long x){
cnt=0;
long long tmp=x;
for(int i=1;prime[i]<=tmp/prime[i];i++){
factor[cnt][1]=0;
if(tmp%prime[i]==0){
factor[cnt][0]=prime[i];
while(tmp%prime[i]==0){
factor[cnt][1]++;
tmp/=prime[i];
}
cnt++;
}
}
if(tmp!=1){
factor[cnt][0]=tmp;
factor[cnt++][1]=1;
}
return cnt;
}
long long ksm(long long a,long long b){
long long res=1;
long long tmp=a%mod;
while(b){
if(b&1){
res*=tmp;
res%=mod;
}
b>>=1;
tmp*=tmp;
tmp%=mod;
}
return res;
}
long long sum(long long p,long long n){
if(p==0)return 0;
if(n==0)return 1;
if(n&1){
return((1+ksm(p,n/2+1))%mod*sum(p,n/2)%mod)%mod;
}
else
return((1+ksm(p,n/2+1))%mod*sum(p,n/2-1)+ksm(p,n/2)%mod)%mod;
}