10.15 模拟赛
原题场。
A 石子
暑假，概率与期望ppt中的经典例题的一道题。。
考虑令 $ x_i $ 表示第 $ i $ 堆石头在第几次被取。那么有
$ x_1 = sum_i{ [x_i leq x_1] } = 1 + sum_i{[x_i < x_1]} $
两边同时套一个期望，由期望的线性性
$ E(x_i) = 1 + sum_iE([x_i < x_1]) = 1 + sum_i{P([x_i < x_1])} $
然后求的就是第 $ i $ 堆石头比第一堆石头先取的概率。
这个可以感性理解一下，我们要么先取第一堆石头要么先去第 $ i $ 堆石头，其他堆的石头貌似一点作用也没有，因为取了其他的石头不影响这两堆的先后顺序。所以其实概率就是只有两堆石头，随机取，取到 $ i $ 堆的概率，就是 $ frac{a_i}{a_1 + a_i} $
对这个求和就好了。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
using namespace std;
//#define int long long
typedef long long ll;
#define MAXN 200006
#define MAXM 450
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
#define cmx( a , b ) a = max( a , b )
#define cmn( a , b ) a = min( a , b )
#define upd( a , b ) ( a = ( a + b ) % P )
//#define P 1000000007
int n;
int a[MAXN];
void read( signed& x ) {
scanf("%d",&x);
}
void read( ll& x ) {
scanf("%lld",&x);
}
long double res = 0.0;
int main() {
read( n );
for( int i = 1 ; i <= n ; ++ i ) {
read( a[i] );
if( i != 1 ) res += ( long double ) a[i] / ( a[i] + a[1] );
}
res += 1.0;
printf("%.8Lf",res);
}
/*
* Things you should pay attention to
* inf is big enough?
* out of bounds?
* long long ?
*/
B 内存
首先，$ O( nmlog ) $ 的做法都会，就是枚举一下增加的数，然后二分判断就好了。
但是如何优化这个东西呢？可以考虑给增加的数字 $ (1 , m-1) $ 随机打乱，每次如果无法使当前答案更优秀就不继续选了。
为啥这样很优秀呢？我们假设对于新循环到的一个数 $ x $ ，新的这个数字比所有当前的数字都小的概率只有 $ frac{1}{i} $，所以最后期望只会跑 $ ln(n) $ 次二分check，总复杂度是 $ O(nm) $
其实这个结论挺可推广的呢！
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
using namespace std;
//#define int long long
typedef long long ll;
#define MAXN 200006
#define MAXM 450
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
#define cmx( a , b ) a = max( a , b )
#define cmn( a , b ) a = min( a , b )
#define upd( a , b ) ( a = ( a + b ) % P )
//#define P 1000000007
int n , m , k , blo;
int A[MAXN] , S[MAXN] , smid[MAXN];
void read( signed& x ) {
scanf("%d",&x);
}
void read( ll& x ) {
scanf("%lld",&x);
}
int a[MAXN];
bool chk( int x ) {
int cur = 0 , kel = 0;
for( int i = 1 ; i <= n ; ++ i ) {
if( a[i] > x ) return false;
if( cur + a[i] > x ) cur = a[i] , ++ kel;
else cur += a[i];
}
if( cur ) ++ kel;
return kel <= k;
}
int P[MAXN];
int main() {
cin >> n >> m >> k;
blo = log2( n );
for( int i = 1 ; i <= n ; ++ i ) read( A[i] ) , a[i] = A[i];
int l = 0 , r = 1e9;
while( l <= r ) {
int mid = l + r >> 1;
if( chk( mid ) ) r = mid - 1;
else l = mid + 1;
}
int cures = l;
for( int i = 1 ; i < m ; ++ i )
P[i] = i;
random_shuffle( P + 1 , P + m );
for( int i = 1 ; i < m ; ++ i ) {
int j = P[i];
for( int i = 1 ; i <= n ; ++ i ) a[i] = ( A[i] + j ) % m;
if( ! chk( cures - 1 ) ) continue;
int l = 0 , r = cures - 1;
while( l <= r ) {
int mid = l + r >> 1;
if( chk( mid ) ) r = mid - 1;
else l = mid + 1;
}
cures = l;
}
printf("%d
",cures);
}
/*
* Things you should pay attention to
* inf is big enough?
* out of bounds?
* long long ?
*/
C 子集
如果把 $ n $ 分解质因数，$ n = prod_i p_i^{c_i} $ ，对于每一个素数，必然有至少一个子集中的数不含这个因子，同时也必然有一个子集中的数字含有这个数字的 $ c_i $ 次方。然后就可以考虑容斥了！
正常的容斥是所有情况减去不存在 0 次方的情况， 再去掉不存在 $ c_i $ 的情况，然后加上不存在的情况就好了。
这样的情况数是 $ 4^k $ 的，$ k $ 最大是 16 左右，所以挂掉了。
但是我们注意到 不存在0次方和不存在 $ c_i $ 次方的情况对答案的贡献是一样的！（都少了一个）所以可以 合并考虑。然后复杂度就是 $ 3^k $ 了
怎么质因数分解呢？简单的做法是直接 $ Pollard-Rho $ ，但是我们也可以对 $ 10^6 $ 内的约数给拿出来，$ m $ 最多只有2个大于 $ 10^6 $ 的质数相乘，则 $ m = p , p^2 , pq $ 这三种形式。而且我们不关系分解后究竟是多少，我们只关心每个质数的系数，所以这样就可以了。
死因：Miller-robbin 没龟速乘。。。。
后面还有一个python版本的
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<bitset>
#include<set>
using namespace std;
#define int long long
typedef long long ll;
#define MAXN 200006
#define MAXM 450
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define inf 0x3f3f3f3f
#define cmx( a , b ) a = max( a , b )
#define cmn( a , b ) a = min( a , b )
#define upd( a , b ) ( a = ( a + b ) % P )
#define P 998244353
int n;
void read( signed& x ) {
scanf("%d",&x);
}
void read( ll& x ) {
scanf("%lld",&x);
}
inline ll mul(ll a,ll b,ll p){
a %= p; b %= p;
if(p<=1e9)return 1ll*a*b%p;
if(p<=1e12)return (((a*(b>>20)%p)<<20)%p+a*(b&(1<<20)-1))%p;
ll d=1ll*floor(a*(long double)b/p);
ll res=(a*b-d*p)%p;if(res<0)res += p;
return res;
}
int power(int x, int a , int p) {
int cur = x % P , ans = 1;
while( a ) {
if( a & 1 ) ans = mul( ans , cur , p );
cur = mul( cur , cur , p ) , a >>= 1;
}
return ans;
}
bool prime(int x) {
for(int i = 1; i <= 30; i++) {
int p = 1ll * rand() * rand() % x * rand() % x + 1;
while(p == x) p = 1ll * rand() * rand() % x * rand() % x + 1;
if(power(p, x - 1 , x) != 1) return false;
}
return true;
}
int val[MAXN], tp , ans = 0;
void dfs(int now, int rev) {
if(now == tp + 1) {
int tmp = 1;
for( int i = 1; i <= tp; i++ ) tmp *= (val[i] + 1), tmp %= P - 1;
ans = (ans + rev * (power(2, tmp , P) - 1) ) % P;
return;
}
dfs(now + 1, rev);
if(val[now] >= 1) -- val[now] , dfs(now + 1, (P - 2) * rev % P), ++ val[now];
if(val[now] >= 2) val[now] -= 2, dfs(now + 1, rev), val[now] += 2;
}
signed main() {
srand( 19260817 );
read( n );
for(int i = 2 ; i <= 1000000 && n > 1; i++) { // primes lower than 1e6
if( !( n % i ) ) ++ tp;
while( !( n % i ) ) val[tp]++ , n /= i;
}
if(n > 1) {
if( prime(n) ) val[++tp] = 1; // n == prime * ppp
else if( (int)sqrt(n) * (int)sqrt(n) == n ) val[++tp] = 2; // n == prime * prime * ppp
else val[ ++tp ] = 1, val[ ++tp ] = 1; // elsewhise, val = 1
}
dfs(1, 1);
cout << ( ans + P ) % P ;
}
/*
* Things you should pay attention to
* inf is big enough?
* out of bounds?
* long long ?
*/
import random
import math
n = 0
P = 998244353
def power( x , a , p ):
cur = x % p
ans = 1
while( a ):
if( a & 1 ):
ans = ans * cur % p
cur = cur * cur % p
a >>= 1
return ans
def prime( x ):
for i in range( 1 , 31 ):
p = random.randint( 1 , x - 1 )
if( power( p , x - 1 , x ) != 1 ):
return 0
return 1
val = []
tp = 0
ans = 0
def dfs( now , rev ):
global tp , ans , P
if( now == tp + 1 ):
tmp = 1
for i in range( 1 , tp + 1 ):
tmp = tmp * ( val[i] + 1 ) % ( P - 1 )
ans = ( ans + rev * ( power( 2 , tmp , P ) - 1 ) ) % P
return
dfs( now + 1 , rev )
if( val[now] >= 1 ):
val[now] = val[now] - 1
dfs( now + 1 , ( P - 2 ) * rev % P )
val[now] = val[now] + 1
if( val[now] >= 2 ):
val[now] = val[now] - 2
dfs( now + 1 , rev )
val[now] = val[now] + 2
return
n = int(input())
val.append( 0 )
for i in range( 2 , 1000001 ):
if( n <= 1 ):
break
if( n % i == 0 ):
tp = tp + 1
val.append( 0 )
while( n % i == 0 ):
val[tp] = val[tp] + 1
n //= i
if( n > 1 ):
if( prime( n ) == 1 ):
tp = tp + 1
val.append( 1 )
else:
if( int(math.sqrt( n )) * int( math.sqrt( n ) ) == n ):
tp = tp + 1
val.append( 2 )
else:
tp = tp + 1
val.append( 1 )
tp = tp + 1
val.append( 1 )
dfs( 1 , 1 )
print( ( ans + P ) % P )