【BZOJ 4725】[POI2017] Reprezentacje ró?nicowe

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4725
神犇题解:http://blog.csdn.net/lych_cys/article/details/53455978

解题报告

这题看上去一脸不可做QwQ
前前后后想了差不多三个小时吧?
突然反应过来:从第63项开始$a(x)$就大于$10^9$了
换一句话来说:之后的每一项,只可能减去前一项才可能小于$10^9$

于是我们把前$63$项之内的拿出来暴力搞一搞
$63$项之后的,我们可以推公式推出来答案是多少

Code

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

const int N = 10000;

int n,tot,vis[N],L[N],R[N],que[N];
LL f[N];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void insert(int w) {
	for (int i=w-1;i;i--) {
		if (abs(f[w]-f[i]) >= N) break;
		vis[abs(f[w]-f[i])] = 1;
	}
} 

inline int query() {
	for (int i=1;i;i++)
		if (!vis[i]) return i;
}

inline void Get_Ans(int w, int id) {
	for (int j=2;j;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] == w) {
				L[id] = i; R[id] = j;
				return;
			}
		}
	}
}

inline void query(int w) {
	for (int j=2;j;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] == w) {
				cout<<j<<' '<<i<<endl;
				return;
			}
		}
	}
}

int main() {
	f[1] = 1; f[2] = 2; vis[1] = 1;
	for (int i=3;i<=120;i++) { 
		if (i&1) f[i] = f[i-1] << 1;
		else f[i] = f[i-1] + query();
		insert(i);
	} 
	for (int j=2;j<=63;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] > 1e9) continue;
			que[++tot] = f[j] - f[i];
		}
	} 
	que[++tot] = (1e9) + 10;
	sort(que+1, que+1+tot);
	for (int i=1;i<tot;i++) Get_Ans(que[i], i); 
	for (int q=read(),x,p;q;q--) {
		x = read();
		p = lower_bound(que+1, que+1+tot, x) - que;
		if (que[p] == x) printf("%d %d\n",R[p], L[p]);
		else if (x <= 90) query(x);
		else printf("%lld %lld\n",(x-90-p+62)*2ll+120,(x-90-p+62)*2ll+119);
	}
	return 0;
}

【Codeforces 757E】Bash Plays with Functions

相关链接

题目传送门:http://codeforces.com/problemset/problem/757/E
官方题解:http://codeforces.com/blog/entry/49743

解题报告

这题窝萌需要打很多的表来发现以下规律:

Ⅰ. 设$x$的素因子种类数为$g(x)$那么$f_0(x)$等于$2^{g(x)}$
Ⅱ. 由规律Ⅰ可得,$f_0(x)$为积性函数,又$f_i(x)=f_{i-1} * 1(x)$,于是我们可用归纳证明得$f_i(x)$均为积性函数
Ⅲ. 设$p$为素数,$f_r(p^k)$与$p$无关,且满足递推式:$f_r(p^k)=\sum\limits_{i=0}^{k}{f_{r-1}(p^i)}$

于是我们预处理出$f_r(p^k)$
对于每次询问,使用积性函数的性质,拆成很多质因数的幂次来做可以辣!
时间复杂度:$O((q+r) \log n)$

Code

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

const int N = 1000009;
const int MOD = 1000000007;

int tot,vis[N],pri[N],sur[N],g[N][21];

inline int read() {
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

inline void prework() {
	for (int i=2;i<N;i++) {
		if (!vis[i]) pri[++tot] = i, sur[i] = i;
		for (int j=1;j<=tot&&i*pri[j]<N;j++) {
			vis[i*pri[j]] = 1; sur[i*pri[j]] = pri[j];
			if (i % pri[j] == 0) break;
		}
	}	
	g[0][0] = 1;
	for (int i=1;i<=20;i++) g[0][i] = 2;
	for (int i=1;i<N;i++) {
		for (int j=0;j<=20;j++) {
			g[i][j] = ((j? g[i][j-1]: 0) + g[i-1][j]) % MOD;
		}
	}
}	

inline int solve(int a, int b) {
	int ret = 1;
	for (int cnt=0,p=sur[b];b>1;cnt=0,p=sur[b]) {
		while (b % p == 0) b /= p, cnt++;
		ret = (LL)ret * g[a][cnt] % MOD;
	}
	return ret;
}

int main() { 
	prework();
	for (int T=read(),a,b;T;T--) {
		a = read(); b = read();
		printf("%d\n",solve(a,b));
	}
	return 0;
}

【BZOJ 1053】[HAOI2007] 反素数ant

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1053
神犇题解:http://medalplus.com/?p=2105

题解

这种题看一眼就会去想找规律吧?
打个表看一看大概是这样:

于是我们可以找到如下规律:
1.质因数是连续的,也就是说我们只用考虑37及之前的质因数
2.较大的质因数个数一定少于较小的质因数的个数

于是我们就可以写个深搜
枚举出所有符合条件的数
然后用这些数去更新答案辣!

Code

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

const int SZ = 12;

int n,num,vout,pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37};

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int DFS(int t, int last, int w, int v) {
	if (t == 13) {
		if (v == num) {
			vout = min(vout, w);
		} else if (v > num) {
			vout = w;
			num = v;
		}
	} else {
		for (int i=0,cur=1;i<=last;i++,cur*=pri[t]) {
			if ((LL)cur * w > n) break;
			else {
				DFS(t+1, i, w*cur, v*(i+1));
			} 
		}
	}
}
 
int main(){
	if ((n=read()) == 1) {
		puts("1");
	} else {
		DFS(1,30,1,1);
		printf("%d\n",vout);
	}
	return 0;
}

【BZOJ 4513】[SDOI2016] 储能表

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4513

先来%一波Menci的强行找规律(:з」∠)https://dn-menci.qbox.me/sdoi2016-table/
然后就是std用的数位DP:http://www.ruiker1997.tk/bzoj-4513

一直感觉这个题目的数位DP很牵强
于是一直尝试使用以前的数位DP的写法来写
然后发现,嘴巴ac还是挺容易的,但真要写出来,还真心不好写
于是代码就算了吧。

—– UPD 2016.9.29 —–
还是补一份代码吧
以前数位DP都不是这么写的
不过感觉这么写,如果没有多组询问还是挺清真的

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

LL f[62][2][2][2],g[62][2][2][2],n,m,MOD,k; 

int main(){
	int T; cin>>T; while (T--) {
		cin>>n>>m>>k>>MOD;
		memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
		g[61][0][0][0] = 1;
		for (int i=60;~i;i--) {
			int t1 = (n>>i)&1, t2 = (m>>i)&1, t3 = (k>>i)&1;
			for (int a=0;a<2;a++) for (int b=0;b<2;b++) for (int c=0;c<2;c++) if (g[i+1][a][b]) {
				for (int x=0,w,wa,wb,wc;x<2;x++) for (int y=0;y<2;y++) {
					if (w=x^y, (!a&&x>t1) || (!b&&y>t2) || (!c&&w<t3)) continue;
					wa = (a||x<t1); wb = (b||y<t2); wc = (c||w>t3);
					(g[i][wa][wb][wc] += g[i+1][a][b]) %= MOD;
					(f[i][wa][wb][wc] += ((f[i+1][a][b] + (((w-t3)*((1LL<<i)%MOD))%MOD)*g[i+1][a][b]%MOD)%MOD + MOD) % MOD) %= MOD;
				}
			}
		}	
		cout<<f[0][1][1][1]<<endl;
	}
	return 0;
}