题解 P5589 【小猪佩奇玩游戏】

· · 题解

放一篇不太一样的题解（大雾

首先考虑将题目转化成图论模型，让 i 向 i^k 连一条边，然后可以发现这样会连出来很多张独立的图，容易发现每张图的贡献独立，所以加起来即可

然后会发现这些图都长一个样

不妨设当前被考虑到的点为 x，那么此时图中应该有x^2,x^3,x^4,...x^k

然后会发现这些图对于答案的贡献之和此图的大小有关，而图的大小又是\log级的

于是问题转化为给定一个大小为x(x\le 30)的图，每次可以随机删掉一个数和其倍数，求删完的期望次数。

就会想到写个状压去算某一张图的贡献...

当然状压的确是可以将答案算出来的，但是复杂度是O(2^{30})而且空间开销相同所以本机是完全跑不出来的...(至少我这里是

于是就会想到真的需要的dp值只有dp[1_2],dp[11_2],dp[111_2]...dp[111111...111_2]

然而这些状态实际上依赖的状态存在大量相同而且真正有效的dp不多所以可以用一个\rm map将有效的dp存下来

但是这样还是很慢

所以就会想到要打表

提前用dp将图的大小为x的时候的期望算出来，然后枚举一个数x计算出图的大小并将被用到的点标记，单次复杂度O(n)

但是实际上对于某一个x如果x>\sqrt n且不存在一个i满足i^k=x那么显然 x 对于答案的贡献为1

于是真正要计算的点就只有1-\sqrt n的这些数

复杂度大约是O(T\sqrt n)

然后要特判1

Code: 
#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register 
#define int long long
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 35000 ; 
const int M = 35 ;
double Ans[M] = { 0, 1.0, 1.5, 2.0, 2.33333333333333, 2.83333333333333, 3.08333333333333,
3.5833333333333, 3.8333333333333, 4.16666666666667, 4.4166666666667, 4.91666666666667, 5.08333333333333, 5.58333333333333,
5.8333333333333, 6.0833333333333, 6.28333333333333, 6.7833333333333, 6.95, 7.45, 7.61666666667, 
7.8666666666667, 8.11666666666667, 8.6166666666667, 8.741666666667, 9.075, 9.325, 9.575, 9.741666666667,
10.2416666666667, 10.3666666666667 };
int n, vis[N], rU ;  
signed main()
{
    int T = gi() ;
    while( T-- ) {
        n = gi() ; int cnt = sqrt(n), k = 0, j ;
        if( cnt * cnt <= n ) ++ cnt ; 
        double ans = 1 ; rU = n - cnt ;
        memset( vis, 0, sizeof(vis) ) ;
        rep( i, 2, cnt ) {
            if( vis[i] ) continue ; 
            for( j = i, k = 0; j <= n; j *= i, ++ k ) {
                if( j > cnt ) -- rU ; 
                else vis[j] = 1 ; 
            } ans += Ans[k] ; 
        } 
        if( cnt <= n ) printf("%.8lf\n", ans + rU ) ;
        else printf("%.8lf\n", ans ) ;
    } 
    return 0 ;
}

打表程序：

#include<bits/stdc++.h>
using namespace std ;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int M = 35 ; 
double Ans[M] ; 
int m ; 
int get( int x ) {
    int ans = 0 ; 
    while( x ) ans += ( x & 1 ), x >>= 1 ;
    return ans ; 
}
map<int, double> dp ;
double Dp( int i ) {
    if( dp[i] || i == 0 ) return dp[i] ; 
    int len = get(i) ;
    for( re int j = 1; j <= m; ++ j ) {
        if( ( 1 << ( j - 1 ) ) & i ) {
            int rk = 0 ;
            for( re int k = j; k <= m; k += j ) {
                if( ( 1 << ( k - 1 ) ) & i ) rk |= ( 1 << ( k - 1 ) ) ;
            }
            dp[i] = ( dp[i] + ( 1.0 / len ) * ( 1.0 + Dp(i ^ rk) ) ) ;
        }
    }
}
signed main()
{

    m = 30 ; int maxn = ( 1 << m ) - 1, rnt = 1 ; 
    printf("%d\n", m ) ;
    for( re int rnt = 1; rnt <= m; ++ rnt ) {
        printf("%d %.8lf\n", rnt, Dp( ( 1 << rnt ) - 1 ) ) ; 
    }
    return 0 ;
}