开个博客，一来作为总结，二来提醒自己还有很多内容需要不断完善。
A - 整数分解为2的幂(51Nod 1383)
课上学习了聚聚的代码，以及划分子问题的思想。
考虑数 n = 1+2+4+……，即1和其他2次幂，其他2次幂提取出2，又变为子问题求解。
#include <cstdio>
const int maxn = 1e6+10;
#define LL long long
const LL mod = 1e9+7;
LL a[maxn];
LL dfs(int n){
if(n <= 1) return 1;
if(a[n]) return a[n];
if(n & 1){
return a[n] = dfs(n-1)%mod;
}else{
return a[n] = (dfs(n-1)%mod + dfs(n/2)%mod) % mod;
}
}
int main(){
int n;
while(scanf("%d", &n) != EOF){
printf("%lld\n", dfs(n));
}
return 0;
}
B - Permutations(poj 2369)
Thinking:
看完题目，可以想到是置换群的知识。
置换：有限集合S到自身的一个一一映射叫做一个置换，即n个元的一种排列变为另一种排列。
题目里的Pn(k)可以看作置换的乘积。
题目思路是求置换中循环节长度，再求其最小公倍数。
最小公倍数求法是a*b/gcd(a,b)。
循环节长度此处用dfs()遍历求得。
#include <cstdio>
bool vis[1005];
int a[1005];
int num;
//求每个循环节的长度
void dfs(int n){
if(vis[n]) return;
vis[n] = true;
num++;
dfs(a[n]);
}
int gcd(int a, int b){
return b ? gcd(b, a%b) : a;
}
int lcm(int a, int b){ //最小公倍数
return a/gcd(a, b)*b;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1; i<=n; i++){ scanf("%d",&a[i]); }
int k = 1;
for(int i=1; i<=n; i++){
if(!vis[i]){
num=0;
dfs(i);
k = lcm(k, num);
}
}
printf("%d",k);
return 0;
}
C - Invoker
Thinking:
最开始对题意有了错误理解，（错误想法原因是看不懂题目所以瞎猜样例），错误思路：利用容斥原理，分An种情况，即Ai代表用i(1<=i<=m)种元素组成n个元素的技能，然后思考消去重复部分，然后就没有然后了。
下来我参考了ppt的课后提示，是标准的polya定理题。（这个定理现在还不是很懂）
参考了ppt中旋转和翻折置换的公式，不等价方案数的性质等概念还很模糊。
参考别人的代码勉强过了这题。
还有就是关于求组合数的两种方法：1、打表。 2、逆元求组合数。
还有就是关于逆元的求法： 1、扩展欧几里得算法。 2、费马小定理。
这个参考博客
#include <cstdio>
#define LL long long
const LL maxn(10010), mod(1e9+7);
LL pow(LL a, LL n, LL p){
LL ans = 1;
while(n){
if(n&1) ans = ans * a % p;
a = a * a % p;
n >>= 1;
}
return ans;
}
LL niyuan(LL a, LL b){
return pow(a, b-2, b);
}
LL gcd(LL a, LL b){
return b==0 ? a : gcd(b, a%b);
}
LL polya(LL m, LL n){
LL i, ans=0;
//旋转
for(i=1; i<=n; i++){
ans = (ans + pow(m, gcd(i,n),mod))%mod;
}
//翻转
if(n&1){
ans = (ans + n*pow(m, (n+1)/2, mod))%mod;
}else{
ans = (ans + n/2*(pow(m,n/2+1, mod) + pow(m, n/2, mod))%mod)%mod;
}
ans = ans%mod*niyuan(2*n,mod)%mod;
return ans;
}
int main(){
int cas;
scanf("%d",&cas);
for(int ca=1; ca<=cas; ca++){
int n,m;
scanf("%d%d",&m, &n);
printf("Case #%d: %lld\n",ca, polya(m,n));
}
return 0;
}
update(2018-08-31)
Burnside定理：如果某一个方案s经过一个置换f后不变，则称s为f的不动点，将f的所有不动点数目记为c(f)，那么等价类数目就等于所有c(f)的平均值。
polya定理：如果将置换f分解成m(f)个循环的乘积，每个循环内所有格子的颜色必须相同。并假设涂k种颜色的话，那么c(f)等于k^m(f)。 得： 等价类的个数就是所有置换的k^m(f)的平均值。
本题是等价类计数问题，有两种置换：旋转和翻折。训练指南147页。
D - Aeroplane chess
想起课上那个饮料问题，求平均次数即求期望。与此题相似，找递推公式。
状态定义：dp[i]为扔筛子期望数。
看ppt提示说逆推，想了想，发现确实如此，因为正推时有多个起点且概率不等，枚举时无法计算。
逆推时分两种情况：1、飞行点和起点以及终点不用投筛子。 2、其他点则枚举筛子6个等概率点。
再扔一次筛子期望加一，因为枚举计算的是下一个状态的期望，当前状态则需要多仍一次才可以。
#include <cstdio>
#include <cstring>
const int N(100010);
int flight[N];
double dp[N];
int main(){
int n,m;
while( scanf("%d%d", &n, &m) && (n||m) ){
memset(flight, -1, sizeof(flight));
for(int i=0; i<m; i++){
int x,y;
scanf("%d%d",&x, &y);
flight[x] = y;
}
memset(dp, 0, sizeof(dp));
for(int i=n-1; i>=0; i--){
if(flight[i] != -1){
dp[i] = dp[flight[i]];
}else{
dp[i] = 1;
for(int j=i+1; j<=i+6; j++){
dp[i] += 1.0/6*dp[j];
}
}
}
printf("%.4lf\n", dp[0]);
}
return 0;
}
后面还有很多题，奈何水平有限，所以慢慢补吧。