HGOI 20190828 题解

ゝ一纸荒年。 2023-06-05 11:26 22阅读 0赞

**Problem A 数学题**

> 设数论函数$f(x)$表示$x(x ∉ Prime)$的次大因数，
> 
> 给出$l,r$求出$\\sum\\limits\_\{i=l,i ∉ Prime\} ^r f(i)$ 。
> 
> 对于$100\\%$的数据,$1 \\leq l\\leq r\\leq 5\\times 10^9$

Solution : 我们思考对于$r-l \\leq 10^7$怎么处理，

显然，$f(x) = \\frac\{x\}\{d\_\{min\}(x)\}$

所以，我们可以用$\\sqrt\{5\\times 10^9\}$的数字去筛区间内的数，找出这些数的$d\_\{min\} (x)$

这样，我们可以在$O(r-l)$的复杂度内解决题目。

但是，对于$100\\%$的数据还不足以通过，所以，我们考虑在本地打表，以$10^7$的间隔打表。

于是，分块打表产生的AC程序就诞生了。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 100005;
    ll a[505] = {
         0,16504974832918ll,49514807041302ll,82524641299076ll,115534479934505ll,148544254405234ll,181554158308885ll,214563872594611ll,247573764207188ll,280583538103016ll,313593361626057ll,346602992946568ll,379613110929775ll,412622718262607ll,445632601916252ll,478642437755379ll,511652194457614ll,544661947496041ll,577671637940336ll,610681752050814ll,643691404588574ll,676701244176651ll,709711054775594ll,742720800286221ll,775730381310093ll,808740585896190ll,841750243027296ll,874760117073666ll,907769696410853ll,940779525226536ll,973789738206002ll,1006799160955474ll,1039808877324861ll,1072819018026025ll,1105828761150350ll,1138838541727837ll,1171848079131282ll,1204858104382139ll,1237867536035320ll,1270877842610423ll,1303887672241912ll,1336897155489979ll,1369907175171416ll,1402916647740933ll,1435927028696641ll,1468936230981939ll,1501946419251818ll,1534955574922012ll,1567966183816364ll,1600975595444924ll,1633985443056901ll,1666995678674159ll,1700005364180681ll,1733014763642307ll,1766024840505475ll,1799034631307151ll,1832044002952252ll,1865054030679522ll,1898064068452051ll,1931073520776903ll,1964083598976891ll,1997093098588907ll,2030103003059564ll,2063112702217827ll,2096122737310551ll,2129133054850411ll,2162142198328595ll,2195152115983905ll,2228161264785474ll,2261172544708734ll,2294181378777450ll,2327191233379424ll,2360201373720367ll,2393211269318476ll,2426220486575075ll,2459230819150224ll,2492240046752302ll,2525251064525340ll,2558259845985451ll,2591268636654841ll,2624280077930602ll,2657288734859772ll,2690299477550963ll,2723308150991146ll,2756319304183776ll,2789328790852636ll,2822338626083272ll,2855347891381860ll,2888357969641819ll,2921367932058355ll,2954377671380517ll,2987387687179118ll,3020395919679682ll,3053407972625776ll,3086417613231907ll,3119426240525339ll,3152436403285179ll,3185446530826116ll,3218455004607940ll,3251466542904717ll,3284474102416981ll,3317485456042933ll,3350494835559564ll,3383505323561767ll,3416514694107384ll,3449524616389762ll,3482535136132263ll,3515544067001265ll,3548552960601121ll,3581563404252177ll,3614573730318868ll,3647583278380671ll,3680593224979870ll,3713603049026829ll,3746614512962914ll,3779623637711295ll,3812631445796912ll,3845642667207059ll,3878650989452908ll,3911661656239387ll,3944671816767424ll,3977681760271560ll,4010691144633474ll,4043702388095629ll,4076710028369395ll,4109720346259831ll,4142730350170032ll,4175739772832184ll,4208750686895433ll,4241759731456393ll,4274769641755841ll,4307777872223390ll,4340789892971559ll,4373799166736030ll,4406809512953890ll,4439817532702298ll,4472829307111790ll,4505836643327275ll,4538848618830486ll,4571857797045020ll,4604867900156142ll,4637878508493697ll,4670886796634050ll,4703896752766576ll,4736906975045792ll,4769917026147829ll,4802926090607880ll,4835937748578967ll,4868944057292098ll,4901955388347787ll,4934964803726201ll,4967976054354879ll,5000985142582223ll,5033994769269421ll,5067004519698299ll,5100015475381224ll,5133023523525477ll,5166035548680638ll,5199044102202040ll,5232053769509974ll,5265063976719498ll,5298071256992732ll,5331086032306110ll,5364093009886904ll,5397101286590264ll,5430112363775912ll,5463125358224685ll,5496130321891579ll,5529143222333432ll,5562151266937027ll,5595161916107909ll,5628170955930451ll,5661180935315217ll,5694191463640877ll,5727200867537917ll,5760210082013019ll,5793220944569250ll,5826231266751643ll,5859240047889761ll,5892248661408006ll,5925259731715720ll,5958268524424498ll,5991280302232593ll,6024290558811088ll,6057297413541092ll,6090308767576979ll,6123319740301532ll,6156326709064649ll,6189337531550686ll,6222350666231978ll,6255356723766425ll,6288367605824763ll,6321377226929040ll,6354387848727584ll,6387396476006881ll,6420406295019013ll,6453418361894346ll,6486425279806916ll,6519434933117769ll,6552447537063411ll,6585455288301656ll,6618465571313108ll,6651473219530721ll,6684487597609615ll,6717493272112836ll,6750503897921972ll,6783514370819588ll,6816524779187087ll,6849533841224964ll,6882543200522966ll,6915555567048002ll,6948563176458473ll,6981569435885717ll,7014587121946570ll,7047593188567860ll,7080603174566593ll,7113612266982300ll,7146622391827726ll,7179631332633195ll,7212642629393380ll,7245652465198424ll,7278661503882743ll,7311671230143188ll,7344681060552161ll,7377691956846305ll,7410698365443030ll,7443713861235034ll,7476716796858509ll,7509729721125427ll,7542738638892030ll,7575747728275743ll,7608761023356292ll,7641769632981677ll,7674779747704999ll,7707788455568150ll,7740801037220385ll,7773805775344854ll,7806820992857333ll,7839827911666137ll,7872836137053706ll,7905848048044634ll,7938859068637500ll,7971867868233332ll,8004875132181171ll,8037889423443128ll,8070896110232830ll,8103906084599451ll,8136918977662318ll,8169925767524876ll,8202934185046077ll,8235946072038061ll,8268954361637275ll,8301967510589725ll,8334974643904362ll,8367982557462832ll,8400994813545019ll,8434004890087843ll,8467013576718783ll,8500020663978651ll,8533037879707351ll,8566043768970011ll,8599053931450993ll,8632062998388608ll,8665072097208580ll,8698085691961056ll,8731093766071517ll,8764101245824907ll,8797112666888496ll,8830121449268148ll,8863131724440902ll,8896143109833470ll,8929152677519312ll,8962160797626791ll,8995170318618191ll,9028182599892397ll,9061189984462759ll,9094202374215214ll,9127209986538911ll,9160218609463869ll,9193230004788814ll,9226239318764918ll,9259249078019552ll,9292258777511949ll,9325269472475613ll,9358278358670667ll,9391290089218066ll,9424298477932490ll,9457306969271855ll,9490319056893750ll,9523328200440578ll,9556338086313235ll,9589345316007227ll,9622357620373676ll,9655368897041442ll,9688375426730456ll,9721388824503967ll,9754397928198984ll,9787402454672295ll,9820418873814550ll,9853427280754508ll,9886434987872625ll,9919445137206151ll,9952458047898686ll,9985464773711174ll,10018477222500475ll,10051480721951374ll,10084498424737300ll,10117503035880454ll,10150511283380008ll,10183525514995947ll,10216533219700575ll,10249545115462676ll,10282555420096173ll,10315560982306657ll,10348573391185967ll,10381583589631280ll,10414590731461579ll,10447602956176541ll,10480610763020224ll,10513619676792520ll,10546634205927295ll,10579639799250750ll,10612656106927603ll,10645658290948488ll,10678673831958315ll,10711680860306978ll,10744688101131573ll,10777702974875348ll,10810713172243588ll,10843718017801528ll,10876727997999731ll,10909742976356068ll,10942745552837649ll,10975759761937138ll,11008768835479689ll,11041780044438665ll,11074792557248863ll,11107797713588017ll,11140805571789883ll,11173816471269923ll,11206833772230056ll,11239831597194058ll,11272848520003779ll,11305859986584876ll,11338861243119995ll,11371876909802235ll,11404891745082435ll,11437892311766835ll,11470908161801780ll,11503914618689504ll,11536926888562700ll,11569930981965041ll,11602948747128948ll,11635953845463421ll,11668964037083148ll,11701974936299703ll,11734983722393772ll,11767999922030689ll,11801002552735713ll,11834012757000273ll,11867024891777099ll,11900034039336811ll,11933044843810804ll,11966053496685306ll,11999059688845505ll,12032073112983797ll,12065079677645057ll,12098093861265145ll,12131099246321317ll,12164116113639448ll,12197123648653031ll,12230130206829220ll,12263140303351556ll,12296149675284303ll,12329166546109808ll,12362163995178362ll,12395183521502911ll,12428191025607568ll,12461197969424400ll,12494210960510352ll,12527223649818333ll,12560226746125306ll,12593237474958756ll,12626250442185141ll,12659255486596395ll,12692269045326660ll,12725280923267732ll,12758287872178920ll,12791300643783440ll,12824306072686417ll,12857318478711430ll,12890328450655256ll,12923342576879840ll,12956346521609668ll,12989354995382276ll,13022368136035560ll,13055375395557624ll,13088387187085464ll,13121392049733620ll,13154414533694357ll,13187414264095104ll,13220422590606727ll,13253434148574342ll,13286449933283688ll,13319453431008458ll,13352467789104963ll,13385472713638835ll,13418484508815598ll,13451496706837476ll,13484505638592382ll,13517515572237834ll,13550521844051264ll,13583534160503278ll,13616544283380142ll,13649549091999822ll,13682567242501910ll,13715571164122745ll,13748585740439504ll,13781593375245859ll,13814596002035274ll,13847616023505842ll,13880624709504762ll,13913623628459146ll,13946645941528622ll,13979654150914934ll,14012656937653649ll,14045669725564142ll,14078684346649165ll,14111685964032611ll,14144700787704032ll,14177709247364616ll,14210718916247011ll,14243734152923032ll,14276736945810726ll,14309744840548250ll,14342760538177797ll,14375768115529314ll,14408777643625614ll,14441784467373423ll,14474800518213737ll,14507806709670214ll,14540822608872175ll,14573824919746354ll,14606839372926299ll,14639849842420486ll,14672858257836917ll,14705862325475290ll,14738881008363594ll,14771885160171399ll,14804896733975004ll,14837906464878693ll,14870916255587693ll,14903917659481655ll,14936947636033735ll,14969940694692679ll,15002951189604675ll,15035967606869556ll,15068968755050047ll,15101989631801975ll,15134994655079856ll,15168005036122695ll,15201009986586199ll,15234028811592968ll,15267031260187832ll,15300045501993724ll,15333049338537562ll,15366062641352998ll,15399073651356570ll,15432082313085917ll,15465089073859934ll,15498098318094652ll,15531118673527436ll,15564119081959673ll,15597131003731861ll,15630136078225767ll,15663155107037699ll,15696160746682461ll,15729168956086495ll,15762183829610629ll,15795182488686761ll,15828210435180516ll,15861208151451320ll,15894213750900732ll,15927236153583087ll,15960235870043580ll,15993247157265286ll,16026259644857776ll,16059270353562328ll,16092274734756367ll,16125292189907530ll,16158300602354326ll,16191300181887807ll,16224324519050731ll,16257330916482853ll,16290331056290523ll,16323345837649990ll,16356351621749496ll,16389374934257625ll,16422373187347681ll,16455390970353283ll,16488403156976175ll};
    ll l, r;
    ll _div[10000005];
    bool nt_prime[N];
    int prime_cnt;
    int prime[N];
    void get_prime(int n) {
        for (int i = 2; i <= n; i++) {
        if (!nt_prime[i]) prime[++ prime_cnt] = i;
        for (int j = 1; j <= prime_cnt && prime[j] * i <= n; j++) {
            nt_prime[i * prime[j]] = 1; 
            if (i % prime[j] == 0) break;
        }
      }
    }
    ll calc(ll l, ll r) {
        memset(_div, 0, sizeof _div);
        ll res = 0;
        for (ll i = 1; i <= prime_cnt; i++) {
        for (ll j = (l - 1) / prime[i] * prime[i] + prime[i]; j <= r; j += prime[i]) {
            if (!_div[j - l]) _div[j - l] = prime[i]; 
        }
      }
        for (ll i = l; i <= r; i++) {
        if (_div[i - l] && _div[i - l] != i) res += i / _div[i - l]; 
      }
        return res;
    }
    ll solve(ll x) {
        ll res = 0; 
        ll w = x / 10000000;
        for (int i = 1; i <= w; i++) res += a[i];
        res += calc(w * 10000000 + 1, x); 
        return res;
    }
    int main() {
        get_prime(1e5); 
        scanf("%lld%lld", &l, &r);
        printf("%lld\n", solve(r) - solve(l - 1));
        return 0; 
    }

A.cpp

**Problem B 假题**

> 给出一棵含有$n$个节点的树，每条边有边权。最大化树中点集，使得点集中的点两两距离大于等于给定的$L$
> 
> 对于$100\\%$的数据满足$1 \\leq n\\leq 5\\times 10^5,1 \\leq L,w\\leq 10^9$
> 
> **数据保证随机生成**

Solution： 直接从$1$跑树的深度，贪心，深度大的优先，用一次dfs除去当前新加入点集的点附近$L$的点。

对于随机数据，复杂度应该是$O(能过)$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(3)
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=5e5+10;
    struct rec{
        int pre,to,w;
    }a[N<<1];
    int d[N],n,l,head[N],tot,p[N];
    bool vis[N];
    bool cmp(int a,int b){
         return d[a]>d[b];}
    inline int read()
    {
        int X=0,w=0; char c=0;
        while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
        while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
        return w?-X:X;
    }
    void adde(int u,int v,int w)
    {
        a[++tot].pre=head[u];
        a[tot].to=v;
        a[tot].w=w;
        head[u]=tot;
    }
    void dfs1(int u,int fa)
    {
        for (int i=head[u];i;i=a[i].pre) {
            int v=a[i].to; if (v==fa) continue;
            d[v]=d[u]+a[i].w; dfs1(v,u);
        }
    }
    void dfs2(int u,int fa,int L)
    {
        if (L<=0) return;
        vis[u]=1; 
        for (int i=head[u];i;i=a[i].pre) {
            int v=a[i].to; if (v==fa) continue;
            dfs2(v,u,L-a[i].w);
        }
    }
    signed main()
    {
        n=read();l=read();
        for (int i=1;i<=n-1;i++) {
            int u=read(),v=read(),w=read();//scanf("%d%d%d",&u,&v,&w);
            adde(u,v,w); adde(v,u,w);
        }
        dfs1(1,0);
        for (int i=1;i<=n;i++) p[i]=i;
        sort(p+1,p+1+n,cmp);
        int ans = 0;
        for (int i=1;i<=n;i++) if (!vis[p[i]]) dfs2(p[i],0,l),ans++;
        printf("%lld\n",ans);
        return 0;
    }

B.cpp

**Problem C 计数题**

> 给出一个序列$a\_i(1 \\leq i \\leq n)$,求出符合下列限制的序列$b\_i (1 \\leq i \\leq 2n)$的个数：
> 
> 1. 对于任意$1 \\leq i \\leq n$,都有$b\_i | b\_\{i+n\}$且$b\_\{i+n\} | a\_i$
> 
> 2. $\\prod\\limits\_\{i=n+1\}^\{2n\} b\_i \\leq \\prod\\limits\_\{i=1\}^\{n\} \{b\_i\}^2$
> 
> 在模$998244353$的意义下输出结果。
> 
> 对于$100\\%$的数据满足，$1 \\leq n\\leq 100,1 \\leq a\_i \\leq 10^9$

Solution :

显然，划分阶段的时候，$i$和$i+n$是一个整体，不可分割。

如果$a\_i$足够小，我们可以直接记$f\[i\]\[j\]$表示当前放到第$i$个和第$i+n$个b序列后半部分乘积除去b序列前半部分的乘积的商为$j$的方案数。

于是这样暴力的状态和dp，是一个$O(n \\prod a\_i \\sqrt\{a\_i\})$的美妙算法，空间复杂度到了阶乘级别。

显然，这样状态数就爆炸了，我们不可能将累乘所获得的值记到状态中去，然后我们会思考怎么不将累乘记到附加状态去。

很快，我们会发现根本没办法做，这个状态不得不记。

敏锐的观察到有一个$a\_i = 2^k$的部分分，因子只有一个！附加状态显然可以用对数优化到$log\_2 a\_i$级别。

由于因数的对称性，即以$\\sqrt\{a\_i\}$为对称轴，大于$\\sqrt\{a\_i\}$和小于$\\sqrt\{a\_i\}$的因数个数都是一样的。

由于选择的数，都是独立的，互不干扰，那么满足$\\prod\\limits\_\{i=n+1\}^\{2n\} b\_i \\leq \\prod\\limits\_\{i=1\}^\{n\} \{b\_i\}^2$和满足$\\prod\\limits\_\{i=n+1\}^\{2n\} b\_i \\geq \\prod\\limits\_\{i=1\}^\{n\} \{b\_i\}^2$的序列个数都是一样的。

对于不考虑第二个限制的方案数，比较容易求，就是$\\prod \\frac\{(c+1)(c+2)\}\{2\}$ ，其中$c$表示某个数，某一个因数出现的次数。

于是，我们需要考虑恰好，$\\prod\\limits\_\{i=n+1\}^\{2n\} b\_i = \\prod\\limits\_\{i=1\}^\{n\} \{b\_i\}^2$的方案数。

对于每一个独立的因数，我们都可以按照$2$那样处理(对数记做状态)，如果当前数不是其倍数，那么就直接跳过，继续下面的转移。

最后将每个独立的质因子的答案相乘就是最后的答案。

设$ans1$表示不考虑第二种方案限制的序列个数，$ans2$表示满足$\\prod\\limits\_\{i=n+1\}^\{2n\} b\_i = \\prod\\limits\_\{i=1\}^\{n\} \{b\_i\}^2$的序列个数。

最终的答案就是$\\frac\{ans1+ans2\}\{2\}$

具体的动态规划方程还是比较经典的也没有什么需要特别注意的地方。

复杂度应该是$O(Prime\\\_Num \\times n \\times \\sum\_\{i=1\}^\{n\} log a\_i \\times \{log\_2\}^2 Max\\\{a\_i\\\}))$

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

# include <bits/stdc++.h>
    # define int long long
    using namespace std;
    const int N=105,mo=998244353;
    int f[N][6001],n,a[N],rec[N],t[N];
    bool is_pr[31623];
    int pr[31623];
    vector<int>v;
    int Pow(int x,int n) {
        int ans = 1;
        while (n) {
            if (n&1) ans=ans*x%mo;
            x=x*x%mo;
            n>>=1;
        }
        return ans%mo;
    }
    void EouLaShai(int Lim)
    {
        memset(is_pr,true,sizeof(is_pr));
        is_pr[1]=false;
        for (int i=2;i<=Lim;i++) {
            if (is_pr[i]) pr[++pr[0]]=i;
            for (int j=1;j<=pr[0]&&i*pr[j]<=Lim;j++) {
                is_pr[i*pr[j]]=false;
                if (i%pr[j]==0) break;
            }
        }
    }
    signed main() {
        int inv2=Pow(2,mo-2); EouLaShai(31622);
        int ret1=1;
        scanf("%lld",&n);
        for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
        memcpy(rec,a,sizeof(a));
        for (int i=1;i<=n;i++) {
                for (int j=1;j<=pr[0];j++) {
                if (pr[j]>rec[i]) break;
                if (rec[i]%pr[j]==0) {
                    v.push_back(pr[j]); int c=0;
                    while (rec[i]>1 && rec[i]%pr[j]==0) rec[i]/=pr[j],c++;
                    ret1=ret1*((c+1)*(c+2)/2)%mo;
                }
            }   
            if (rec[i]!=1) ret1=ret1*((1+1)*(1+2)/2)%mo,v.push_back(rec[i]);
        } 
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        int ret2=1;
        for (int tmp=0;tmp<v.size();tmp++) {
            int num = v[tmp],sum=0; 
            for (int i=1;i<=n;i++) {
                t[i]=0; int mht=a[i];
                while (mht>1&&mht%num==0) mht/=num,t[i]++;
                sum+=t[i];
            }
            for (int i=0;i<=n;i++)
             for (int j=-sum;j<=sum;j++)
              f[i][j+3000]=0;
            f[0][0+3000]=1;
            for (int i=0;i<=n-1;i++)
             for (int j=-sum;j<=sum;j++) if (f[i][j+3000]) {
                if (a[i+1]%num!=0) { f[i+1][j+3000]=f[i][j+3000]; continue;}
                int lim = t[i+1];
                for (int k=0;k<=lim;k++)
                 for (int w=0;w<=k;w++) if (j+k-2*w>=-sum &&j+k-2*w<=sum) {
                    f[i+1][j+k-2*w+3000]=(f[i+1][j+k-2*w+3000]+f[i][j+3000])%mo;
                  }
             }
             ret2=ret2*f[n][0+3000]%mo;
        }
        int ans = (ret1+ret2)*inv2%mo;
        printf("%lld\n",ans); 
        return 0;
    }

C.cpp

转载于:https://www.cnblogs.com/ljc20020730/p/11427185.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/24e49f323e7346748a41e659558d1417.png