CXJY-Day 4
FLAG: T3还不会做，记得填坑
闯关大赛（competition）
【题目描述】
因为小A的游戏技巧太过高超，所以他被邀请参加第2019届头号玩家邀请赛，与众多游戏好手同台竞技，决出2019年的头号玩家。
这场比赛一共有n道题目，都是某个游戏中的某个高难度关卡，小A在看到题目后就预估出了自己需要多长时间来解决这个关卡（以秒计时），但是由于那一天小A感冒了，虽然用的是自己最顺手的设备，几乎不怎么可能出现操作失误的问题，但是他有50%的概率会在一个题目中打一个喷嚏，导致他要多花1秒来挽回这个失误。
由于比赛的特殊要求，题目必须按顺序一道一道做下来。
比赛总时长为T，而小A由于担心这个不确定因素，想让你帮他算一算他期望完成的题目个数。
注意，如果在第T秒完成了一道题目，也算是完成了这道题目。
【输入数据】
第一行两个整数n,T，分别表示题目的数量，比赛的事件总长。
接下来一行n个整数，分别表示每一道题目的时长。
【输出数据】
一个整数表示完成题目的期望个数。
答案对$(1e9+7)$取模，即设答案化为最简分式后的形式为$a/b$，其中a和b的互质。输出整数x使得$bx≡a mod (1e9+7)$且$0≤x \le 1e9+7$。可以证明这样的整数x是唯一的。
【样例输入】
3 5
2 2 2【样例输出】
750000007【数据范围】
对于30%的数据，$n≤20，T≤1e6$。
对于60%的数据，$n≤1000，T≤1e9$。
对于100%的数据，$n≤100000，T≤1e12$。每道题目的时长$≤1e9$。
题解
30% 期望的线性加性质，可以dp，$dp[i][j]$表示当前做完第i个任务，时间为j的概率，最后全部求和即可
60% 算出每个点可以完成的概率，即它对答案的贡献，$p=\sum_{i=0}^{T-sumt}{C_c^i}*0.5^c$，其中c为当前的点，sumt为c及之前的时间和
100% 优化60%的求和公式即可，由杨辉三角可知$$\sum_{i=0}^{i}C_{c+1}^{i}=2*\sum_{i=0}^m{C_c^i}-C_c^m$$由于每次的上界$min(i,T-sumt)$变化是单调的，考虑记下每次的前缀和，每次先把$sum=sum*2-C_i^{lastm}$，然后根据新的状态进行增减，并更新lastm即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
ll n,t,a[100005],p[100005],ans;
ll power(ll a,ll b){
ll ret=1;
while (b){
if (b&1) ret=ret*a%mod;
b>>=1;
a=a*a%mod;
}
return ret;
}
ll C(ll a,ll b){
return p[a]*power(p[a-b],mod-2)%mod*power(p[b],mod-2)%mod;
}
int main(){
freopen("competition.in","r",stdin);
freopen("competition.out","w",stdout);
cin>>n>>t;
p[0]=1;
for (int i=1;i<=n;++i){
scanf("%lld",&a[i]);
p[i]=p[i-1]*i%mod;
}
int lastm=0; ll sumc=1,lastc=1,sumt=0;
for (int i=1;i<=n;++i){
sumc=(sumc*2-lastc)%mod;
if (sumc<0) sumc+=mod;
sumt+=a[i];
ll nowm=min((ll)i,t-sumt);
if (nowm<0) break;
if (nowm>lastm){
for (int j=lastm+1;j<=nowm;++j){
lastc=C(i,j);
sumc=(sumc+lastc)%mod;
}
}
if (lastm>nowm){
for (int j=lastm;j>=nowm+1;--j){
lastc=C(i,j);
sumc=sumc-lastc;
if (sumc<0) sumc+=mod;
}
}
lastm=nowm;
lastc=C(i,nowm);
ans=(ans+sumc*power(power(2,i),mod-2)%mod)%mod;
}
cout<<ans<<endl;
return 0;
}户口调查（research）
【题目描述】
小A《都市：天际线》的城市现在人口爆炸，急需做一个人口普查来制定下一步人口计划了。
在调查的过程中，小A看到很多人的生日都是相同的，所以他想要知道，如果有k个人，那么这k个人里面存在两个生日相同的人的概率。
《都市：天际线》这款游戏里面一年比较长，一年有天，每个人的生日相互独立。
【输入数据】
一行两个整数n,k。
【输出数据】
输出两个整数A,B,答案是A/B，且A,B要对(1e6+3)取模，取模前A,B互质。
【样例输入1】
3 2【样例输出1】
1 8【样例输入2】
4 3【样例输出2】
23 128【数据范围】
对于20%的数据，$1≤n,k≤10$。
对于40%的数据，$1≤n≤10,1≤k≤1000$。
对于另20%的数据，$1≤n≤20$。
对于100%的数据，$1≤n,k≤1e18$。
题解
概率为1-每个人生日都不同的方案数
考虑求每个人生日都不同的方案数$$\frac{A_{2^n}^k}{(2^n)^k}=\frac{(2^n)(2^n-1)(2^n-2)\dots(2^n-k+1)}{2^{nk}}$$
由于要先约分，因此要先求出分子中2的倍数，可以发现因子个数为$$n+Cnt_1+Cnt_2+\dots+Cnt_{k-1}$$即每一项的2的因子数由被减的决定，统计时直接$n+(k-1)/2+(k-1)/4+\dots$
发现p很小，当$k>=p$时，$A_{2^n}^k$是连续k个自然数的乘积，就等于0，否则直接暴力求即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,k,mod=1e6+3,ans1,ans2;
ll power(ll a,ll b){
ll ret=1;
while (b){
if (b&1) ret=ret*a%mod;
b>>=1;
a=a*a%mod;
}
return ret;
}
ll get2(ll x){
ll ans=0;
while (x){
ans+=(x/2)%(mod-1);
ans%=mod-1;
x>>=1;
}
return (ans+n)%(mod-1);
}
int main(){
freopen("research.in","r",stdin);
freopen("research.out","w",stdout);
cin>>n>>k;
ll c2=get2(k-1);
ans2=n%(mod-1)*(k%(mod-1))%(mod-1)-c2;
if (ans2<0) ans2+=mod-1;
ans2=power(2,ans2);
if (k>=mod) ans1=0;
else{
ll fl=power(2,n);
ans1=1;
for (int i=0;i<k;++i){
ll tt=fl-i;
if (tt<0) tt+=mod;
ans1=ans1*tt%mod;
}
ans1=ans1*power(power(2,c2),mod-2)%mod;
}
ans1=ans2-ans1;
if (ans1<0) ans1+=mod;
printf("%lld %lld\n",ans1,ans2);
return 0;
}挑战小B（gcdlcm）
【题目描述】
在被小B的问题击败后，小A开始努力学习了，数论是他最近比较喜欢的板块，所以他又想出了一道题目，想要用来击败小B，重新得到自信。
问题是：有一个长度为n的数组A，每一个元素可以取1~m中的任意一个数，很显然，一共有个这样的数组。
问题一共有两种：
对于给定的正整数k，有多少个数组A满足$gcd(Ai)(i=1,2,…,n)=k$
对于给定的正整数k，有多少个数组A满足$k|lcm(Ai)(i=1,2,…,n)$
但是这种题目太简单了，很容易就被小B秒掉了，而小B又加强了一下这道题，请对$[L,R]$范围内的k，求出某种问题的答案，并加起来回答整个问题。
因为答案会很大，所以请对$(1e9+7)$取模。
【输入数据】
第一行两个整数T,type表示数组组数以及数据类型（$type=1$时回答gcd的问题的答案，$type=2$时回答lcm的问题的答案）。
接下来T行每行四个整数$n,m,L,R(1<=L<=R<=m)$表示一次询问。
【输出数据】
T行每行一个整数ans，表示第i次询问的答案，应对$(1e9+7)$取模。
【样例输入1】
5 1
5 5 1 5
5 5 2 5
5 5 3 5
5 5 4 5
5 5 5 5【样例输出1】
3125
34
3
2
1【样例输入2】
5 2
5 5 1 5
5 5 2 5
5 5 3 5
5 5 4 5
5 5 5 5【样例输出2】
12310
9185
6303
4202
2101题解
type=1
$dp[i][j]$为前i个数gcd为j的方案数，然后转移
$f[i]$表示n个数的gcd为i的方案数$$f[i]=(\lfloor m/i \rfloor)^n-f[2*i]-f[3*i]\dots $$从后往前算即可
或者$g[i]$表示n个不大于i的数gcd为1的方案数，$$g[i]=i^n-g[i/2]+g[i/3]\dots$$即总方案数减去gcd为2，3，4…的方案
由此可以发现$f[i]=g[m/i]$，因此当$m/i=m/j$时，$f[i]=f[j]$,由于$\lfloor m/i \rfloor$只有$\sqrt{n}$种取值，因此可以加速递推
type=2
容斥原理，若设$k=p^a,ans=m^n-(m-m/(p^a))^n$,若$k=p^a*q^b,ans=m^n-(m-m/(p^a))^n-(m-m/(q^b))^n+(m-m/(p^a)-m/(q^b)+m/(p^a*q^b))^n$,因为最多有4个因数，因此3，4情况同理
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int M=(int)1e7+5,P=(int)1e9+7;
void Add(int &x,int y){
x+=y;
if(x>=P)x-=P;
}
void Del(int &x,int y){
x-=y;
if(x<0)x+=P;
}
int fast(int x,int p){
int re=1;
while(p){
if(p&1)re=(long long)re*x%P;
x=(long long)x*x%P,p>>=1;
}return re;
}
int Mod(int x){
if(x<0)x+=P;
return x;
}
int n,m,l,r;
int vis[M],mu[M],sum[M],prime[M/10],psz;
struct SHUI{
int fst[M],ps[M],TIM;
int fast(int x,int p){
int &re=fst[x];
if(ps[x]==TIM)return re;
ps[x]=TIM;
re=1;
while(p){
if(p&1)re=(long long)re*x%P;
x=(long long)x*x%P,p>>=1;
}return re;
}
int g(int x){
int re=0;
for(int i=1,a,b;i<=x;){
a=x/i;
b=x/a;
Add(re,(long long)(sum[b]-sum[i-1]+P)*fast(a,n)%P);
i=b+1;
}
return re;
}
void solve(){
TIM++;
int ans=0;
for(int i=l,a,b;i<=r;){
a=m/i;
b=m/a;
if(b>r)b=r;
Add(ans,(long long)g(a)*(b-i+1)%P);
i=b+1;
}
printf("%d\n",ans);
}
}P50;
int cas,tp;
void init1(){
mu[1]=1;
for(int i=2,tp;i<M;i++){
if(vis[i]==0)prime[psz++]=i,mu[i]=-1;
tp=-mu[i];
for(int j=0,t;j<psz&&((t=prime[j]*i)<M);j++){
vis[t]=1;
if(i%prime[j]==0){
mu[t]=0;
break;
}
mu[t]=tp;
}
}
for(int i=1;i<M;i++)sum[i]=sum[i-1]+mu[i];
}
void solve1(){
init1();
while(cas--)scanf("%d %d %d %d",&n,&m,&l,&r),P50.solve();
}
struct UHSI{
int pd[205][205],fac[205];
int dp[205][8];
int pm[5],bin[5];
UHSI(){
for(int i=0;i<5;i++)bin[i]=(1<<i);
fac[0]=1;
for(int i=1;i<205;i++)fac[i]=(long long)fac[i-1]*i%P;
pd[0][0]=1;
for(int i=1;i<205;i++)
for(int j=1;j<205;j++)
Add(pd[i][j]=pd[i-1][j-1],(long long)pd[i][j-1]*i%P);
for(int i=1;i<205;i++)
for(int j=1;j<205;j++)
pd[i][j]=(long long)pd[i][j]*fac[i]%P;
}
int calc(int x){
if(x==1)return fast(m,n);
memset(dp,0,sizeof(dp));
int sz=0;
for(int i=0;prime[i]*prime[i]<=x;i++)
if(x%prime[i]==0){
pm[sz]=1;
while(x%prime[i]==0)x/=prime[i],pm[sz]*=prime[i];
sz++;
}
if(x>1)pm[sz++]=x;
int re=0,up=(1<<sz)-1;
dp[0][0]=1;
for(int i=1,s1;i<=m;i++){
s1=0;
for(int k=0;k<sz;k++)
if(i%pm[k]==0)
s1|=bin[k];
for(int j=i-1;j>=0;j--)
for(int l=up;l>=0;l--)
Add(dp[j+1][s1|l],dp[j][l]);
}
for(int i=1;i<=m;i++)
Add(re,(long long)dp[i][up]*pd[i][n]%P);
return re;
}
void solve(){
int ans=0;
for(int i=l;i<=r;i++)Add(ans,calc(i));
printf("%d\n",ans);
}
}P20;
struct IUHS{
int pm[5],bin[5];
int stk[5],ssz;
IUHS(){
for(int i=0;i<5;i++)bin[i]=(1<<i);
}
int calc(int x){
if(x==1)return fast(m,n);
int sz=0;
for(int i=0;prime[i]*prime[i]<=x;i++)
if(x%prime[i]==0){
pm[sz]=1;
while(x%prime[i]==0)x/=prime[i],pm[sz]*=prime[i];
sz++;
}
if(x>1)pm[sz++]=x;
int re=fast(m,n),up=(1<<sz)-1;
for(int i=1,t;i<=up;i++){
ssz=0;
for(int j=0;j<sz;j++)if(i&bin[j])stk[ssz++]=pm[j];
t=0;
for(int k=0,uup=(1<<ssz),s,c;k<uup;k++){
s=1;
c=0;
for(int l=0;l<ssz;l++)if(k&bin[l])s*=stk[l],c^=1;
if(c)t-=m/s;
else t+=m/s;
}
if(ssz&1)Del(re,fast(t,n));
else Add(re,fast(t,n));
}
return re;
}
void solve(){
int ans=0;
for(int i=l;i<=r;i++)Add(ans,calc(i));
printf("%d\n",ans);
}
}P30;
struct IHSU{
void solve(){
// if(0);
if(n<=200&&m<=200)P20.solve();
else P30.solve();
}
}P50_1;
void init2(){
mu[1]=1;
for(int i=2,tp;i<1005;i++){
if(vis[i]==0)prime[psz++]=i,mu[i]=-1;
tp=-mu[i];
for(int j=0,t;j<psz&&((t=prime[j]*i)<1005);j++){
vis[t]=1;
if(i%prime[j]==0){
mu[t]=0;
break;
}
mu[t]=tp;
}
}
}
void solve2(){
init2();
while(cas--)scanf("%d %d %d %d",&n,&m,&l,&r),P50_1.solve();
}
int main(){
freopen("gcdlcm.in","r",stdin);
freopen("gcdlcm.out","w",stdout);
scanf("%d %d",&cas,&tp);
if(tp==1)solve1();
else solve2();
return 0;
}其他
要做的题
HDU4089
BZOJ4318
POJ2096
HDU4035 Maze
HDU5245 Joyful
HDU5379
概率+期望
莫比乌斯反演(https://blog.csdn.net/ftx456789/article/details/81810237)
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-4/
