写题记录3

1 (UVA1635)

题意：输出 $\sum_{i=1}^{n-1} C_{n-1}^i$ 中被m整除的数

对组合数这种性质的数判断整除肯定是利用唯一分解定理，于是我们可以先对m做一次素数分解，然后根据组合数 $C_n^m = \frac{n-m+1}{m}C_n^{m-1}$ 的性质，可以把各个素因子的数目也递推出来，最后判断各个素因子就好了

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e6+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
int e[N],cnt,prime[N],flag[N];
ll n,m;
int main(){
  // freopen("input.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  while(scanf("%lld%lld",&n,&m) == 2){
    cnt = 0;
    memset(e,0,sizeof(e));
    int bound = sqrt(m+0.5);
    ll num = m;
    vector<int> ans;
    for(int i = 2;i <= bound;i++){
      if(num == 1) break;
      if(num%i == 0){
				prime[++cnt] = i;
				while(num%i == 0){
				num /= i;
			  e[cnt]++;
				}
      }
    }
    if(num != 1) {prime[++cnt] = num;e[cnt] = 1;}
    n--;
    memset(flag,0,sizeof(flag));
    for(int i = 1;i <= cnt;i++){
      int tim = 0;
      for(int j = 1;j < n;j++){
				ll up = n-j+1,down = j;
				while(up%prime[i] == 0){
				  up /= prime[i];
				  tim++;
				}
				while(down%prime[i] == 0){
				  down /= prime[i];
				  tim--;
				}
				if(tim < e[i]) flag[j] = 1;
      }
    }
    for(int i = 1;i < n;i++) if(!flag[i]) ans.push_back(i+1);
    printf("%lu\n",ans.size());
    for(int i = 0;i < ans.size();i++){
      if(i == ans.size()-1) printf("%d\n",ans[i]);
      else printf("%d ",ans[i]);
    }
    if(ans.size() == 0) puts("");
  }
  return 0;
}

2(UVA1639)

题意：对于两个各有n个糖果的盒子，一个人选择打开第一个盒子的概率为p，第二个为1-p，问打开某个盒子以后发现没有糖果了另外一个盒子剩下的糖果数的期望值

显然可以发现：

E(x) = i\times{(\sum_{i=0}^n\tbinom{2n-i}{n}p^{n+1}(1-p)^{n-i}+\sum_{i=0}^n\tbinom{2n-i}{n}(1-p)^{n+1}p^{n-i})}

这种东西一看就不可能正常去算，于是我们可以考虑两边同时取对数，于是可以得到：

\ln{E(x)} = \ln{i}\sum_{i=0}^{n}(\ln{\tbinom{2n-i}{n}}+(n+1)\ln{p}+(n-i)\ln{(1-p)})

而我们又知道 $\tbinom{2n-i}{n} = \frac{(2n-i)!}{n!(n-i)!}$ ，于是就有 $\ln{\tbinom{2n-i}{n}} = \ln{(2n-i)!}-ln{n!}-ln{(n-i)!}$

而对 $\ln{n!}$ 这种式子显然可以通过递推做到，于是就可以在 $\mathcal{O}(n)$ 复杂度内解决本问题。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
typedef long double ld;
const int N = 1e6+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
ld f[N],ans1[N],ans2[N],ans,p;
int n;
int main(){
  // freopen("input.txt","r",stdin);  
  for(int i = 1;i <= 1e6;i++){
    f[i] = f[i-1] + log(ld(i));
  }
  int kase = 1;
  while(scanf("%d %Lf",&n,&p) == 2){
    ans = 0;
    for(int i = 0;i <= n;i++){
      ans1[i] = f[2*n-i] - f[n] - f[n-i] + ld(n+1)*log(p)+ ld(n-i)*log(1.0-p);
      ans2[i] = f[2*n-i] - f[n] - f[n-i] + ld(n+1)*log(1.0-p) + ld(n-i)*log(p);
      ans1[i] = exp(ans1[i]);
      ans2[i] = exp(ans2[i]);
    }
    for(int i = 0;i <= n;i++){
      ans += ld(i)*(ans1[i] + ans2[i]);
    }
    printf("Case %d: %.6Lf\n",kase++,ans);
  }
  return 0;
}

3(UVA 10288)

题意：对于标有1~n数字的彩票，求集齐所有数字所需要彩票的期望

假设已经集齐了k张彩票，不妨令 $s = \frac{k}{n}$ ，那么需要t次才能抽中其他种彩票的概率是 $s^{t-1}(1-s)$ ，所以此时抽中其他种彩票的期望次数就是 $\sum_{i=1}^\infty{i\times[s^{i-1}(1-s)]}$ ，而我们知道 $\sum_{i=1}^\infty is^{i-1} = \frac{1}{(1-s)^2}$ ，所以对于第t次的期望就是 $\frac{1}{1-s} = \frac{n}{n-k}$ ，所以整个的期望就是 $\sum_{i=0}^{k-1} \frac{n}{n-k}$

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e5+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
ll gcd(ll x,ll y){
  if(y == 0) return x;
  else return gcd(y,x%y);
}
int n;
int main(){
  // freopen("input.txt","r",stdin);
  while(cin>>n){
    ll up1 = 1,down1 = 1;
    for(int i = 1;i < n;i++){
      ll up2 = n,down2 = n-i;
      ll up3 = (up1*down2 + up2*down1);
      ll down3 = down1*down2;
      up1 = up3/gcd(up3,down3);
      down1 = down3/gcd(up3,down3);
    }
    if(up1%down1 == 0) cout<<up1/down1<<endl;
    else{
      ll num1 = up1%down1,num2 = down1,num3 = up1/down1;
      string s1 = to_string(num1),s2 = to_string(num2),s3 = to_string(num3);
      for(int i = 1;i <= s3.size()+1;i++) cout<<" ";cout<<s1<<endl;
      cout<<s3<<" ";for(int i = 1;i <= max(s1.size(),s2.size());i++) cout<<"-";cout<<endl;
      for(int i = 1;i <= s3.size()+1;i++) cout<<" ";cout<<s2<<endl;
    }
  }
  return 0;
}

4(UVA580)

题意：对于一个由n个红球和白球组成的排列，求有至少三个红球连在一起的排列数

不妨设 $g(n)$ 为前n个球没有连续三个红球的数目， $f(n)$ 为所求答案，有 $g(n) = 2^n - f(n)$ ，不妨设一个最小的连续单元(白红红红)，则所有排列数可以通过 $ans = 2^{n-3} - \sum_{i=4}^ng(i-4)\times 2^{n-i}$ 来计算(当然这题也可以用DP)

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef double dd;
const int N = 1e5+5;
const dd eps = 1e-8;
const int mod = 1e9+7;
ll f[N],n;

int main(){
  // freopen("input.txt","r",stdin);
  f[0] = 0,f[1] = 0,f[2] = 0,f[3] = 1;
  for(int i = 4;i <= 30;i++){
    for(int j = 4;j <= i;j++){
      ll now = (1<<(i-4)) - (1<<(i-j))*f[j-4];
      f[i] += now;
    }
    f[i] += (1<<(i-3));
  }
  while(cin>>n and n){
    cout<<f[n]<<endl;
  }
  return 0;
}

init0xyz的自留地

1 (UVA1635)

2(UVA1639)

3(UVA 10288)

4(UVA580)

CF补题(9.8-9.13)