首页 > 其他分享 >省选欢乐赛 题解

省选欢乐赛 题解

时间：2023-03-30 18:11:06浏览次数：42  
标签：省选 题解 inv3 int 1ll 欢乐 ans dp mod

昨天沈老师神仙场整不会了。然后今天经典老题。

不是很懂为什么三道题题目名称都是 Delov。

卷王

发现如果答案为第 \(t\) 秒，那么这个序列一定是一个 \(1\)、两个连续的 \(1\)、三个连续的 \(1\)……一直到 \(t\) 个连续的 \(1\)（中间可能有没有的项，即不操作）异或起来。那随便跑个状压就行了。他 \(n\le 16\)，跑起来松松松。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int n;
bool dp[20][20][1<<16];
char s[20];
void solve(int n){
    dp[n][0][0]=1;
    for(int i=1;i<=n;i++){
        int ret=0;
        for(int j=1;j<=i;j++)ret=ret<<1|1;
        for(int j=0;j<(1<<n);j++){
            dp[n][i][j]|=dp[n][i-1][j];
            for(int k=1;k<=n;k++){
                int s=(ret<<k-1)&((1<<n)-1);
                dp[n][i][j^s]|=dp[n][i-1][j];
            }
        }
    }
}
int main(){
    for(int i=1;i<=16;i++)solve(i);
    int tim;scanf("%d",&tim);
    while(tim--){
        scanf("%s",s+1);n=strlen(s+1);int t=0;
        for(int i=n;i>=1;i--){
            t=(t<<1)|(s[i]=='1');
        }
        for(int i=0;i<=n;i++)if(dp[n][i][t]){
            printf("%d\n",i);break;
        }
    }
    return 0;
}

赢王

首先这个操作可以变成前缀和单点 \(\pm 1\)。然后有一个显然的 \(O(n^2)\) 暴力，场上 11:40 开始写写了三分钟写出来了。

然后显然只有相邻的有贡献，贡献是一个显然的式子。

然后不会了，全篇对着 yspm 贺。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
const int mod=998244353;
int n,k,ans,a[1000010],sum[1000010],lsh[1000010],cnt[1000010],cnt2[1000010];
struct BIT{
    int sum[1000010],cnt[1000010];
    #define lowbit(x) (x&-x)
    void update(int x,int num){
        int val=1ll*num*lsh[x]%mod;
        while(x<=n)cnt[x]+=num,sum[x]+=val,x+=lowbit(x);
    }
    int querycnt(int x){
        int sum=0;while(x)sum=(sum+cnt[x])%mod,x-=lowbit(x);return sum;
    }
    int querysum(int x){
        int ans=0;while(x)ans=(ans+sum[x])%mod,x-=lowbit(x);return ans;
    }
}c;
int query(int l,int r,int val,int od){
    return (c.querycnt(r)-c.querycnt(l-1))*val+(c.querysum(r)-c.querysum(l-1))*od;
}
signed main(){
    scanf("%lld%lld",&n,&k);lsh[0]++;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);sum[i]=(sum[i-1]+a[i])%k;
        lsh[++lsh[0]]=sum[i];
    }
    sort(lsh+1,lsh+lsh[0]+1);
    lsh[0]=unique(lsh+1,lsh+lsh[0]+1)-lsh-1;
    ans-=1ll*n*(n+1)/2;
    for(int i=0;i<=n;i++){
        sum[i]=lower_bound(lsh+1,lsh+lsh[0]+1,sum[i])-lsh;
        ans+=cnt[sum[i]];cnt[sum[i]]++;
    }
    cnt[sum[0]]--;cnt2[sum[0]]++;
    c.update(sum[0],cnt[sum[0]]);
    for(int i=1;i<=n;i++){
        ans+=query(lower_bound(lsh+1,lsh+lsh[0]+1,lsh[sum[i]]-k/2)-lsh,sum[i],lsh[sum[i]],-1);
        ans+=query(lower_bound(lsh+1,lsh+lsh[0]+1,lsh[sum[i]]+(k+1)/2)-lsh,lsh[0],lsh[sum[i]]+k,-1);
        ans+=query(1,upper_bound(lsh+1,lsh+lsh[0]+1,lsh[sum[i]]-k/2-1)-lsh-1,k-lsh[sum[i]],1);
        ans+=query(sum[i]+1,upper_bound(lsh+1,lsh+lsh[0]+1,lsh[sum[i]]+(k+1)/2-1)-lsh-1,-lsh[sum[i]],1);
        cnt[sum[i]]--;cnt2[sum[i]]++;
        c.update(sum[i],cnt[sum[i]]-cnt2[sum[i]]+1);
    }
    ans=(ans+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}

稳王

论从 8:20 干到 11:30 拿了 63 分这件事。使用了一页半的算草。挺蚌埠的。

首先一定是攒一波牌然后一轮打掉。期望不会，考虑 PGF 的一般套路，答案就是 \(G(1)\)，\(G\) 是第 \(i\) 轮没结束的概率。直接推 \(G\) 看上去比较可做，把 \(g_0=1\) 去掉，把每个情况拆开：

  1. 全毒：\(\dfrac{1-\left(\frac 13\right)^n}2\)。
  2. 全火：\(\dfrac{1-\left(\frac 13\right)^{\lfloor\frac{n-1}2\rfloor}}2\)。
  3. 全复：\(\frac 12\)。
  4. 火复：\(2\left(1-\left(\dfrac 23\right)^{\lfloor\frac{n-1}2\rfloor}\right)\) 再减掉 \(2\times\) 全火。
  5. 毒火：这时候有个组合数的式子，但是看起来就很不可做的样子。

观察数据范围 \(10^{18}\)，合理猜测是个快速幂。考虑矩阵递推。首先对牌递推不太好办，直接对血递推，然后把没打死的概率加起来。对于毒火，毒伤害是 \(1\)（把第一张毒也算进来），火伤害是 \(3\)。强制都选，可以容斥一下选了几个，也可以暴力 dp 加维：设 \(dp_{i,0/1,0/1}\) 为 \(i\) 点伤害有无毒和火，转移显然。然后就可以矩阵加速递推了。

这是场上的 \(O(n)\) 暴力递推代码。为什么不冲矩阵一会说。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int mod=998244353,inv2=(mod+1)>>1,inv3=(mod+1)/3;
long long n;
int ans;
int qpow(int a,long long b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
int dp[100010][2][2],f[100010][2][2][2];
signed main(){
    int tim;scanf("%lld",&tim);
    while(tim--){
        scanf("%lld",&n);ans=0;
        ans=(ans+inv2+1)%mod;
        ans=(ans+1ll*(1-qpow(inv3,n)+mod)%mod*inv2)%mod;
        ans=(ans-1ll*(1-qpow(inv3,n-1>>1)+mod)%mod*inv2%mod+mod)%mod;
        ans=(ans+2ll*(1-qpow(2ll*inv3%mod,n-1>>1)+mod))%mod;
        dp[0][0][0]=1;
        for(int i=1;i<=n;i++){
            if(i>=1)dp[i][1][0]=1ll*(dp[i-1][1][0]+dp[i-1][0][0])%mod*inv3%mod;
            if(i>=3)dp[i][0][1]=1ll*(dp[i-3][0][1]+dp[i-3][0][0])%mod*inv3%mod;
            if(i>=3)dp[i][1][1]=1ll*(1ll*dp[i-1][0][1]+dp[i-1][1][1]+dp[i-3][1][0]+dp[i-3][1][1])%mod*inv3%mod;
            ans=(ans+dp[i][1][1])%mod;
        }
        for(int i=1;i<=n;i++)dp[i][1][0]=dp[i][0][1]=dp[i][1][1]=0;
        for(int i=1;i<=n;i++){
            if(i>=1)dp[i][1][0]=1ll*(dp[i-1][1][0]+dp[i-1][0][0])%mod*inv3%mod;
            if(i>=2)dp[i][0][1]=1ll*(dp[i-2][0][1]+dp[i-2][0][0])%mod*inv3%mod;
            if(i>=2)dp[i][1][1]=1ll*(1ll*dp[i-1][0][1]+dp[i-1][1][1]+dp[i-2][1][0]+dp[i-2][1][1])%mod*inv3%mod;
            ans=(ans+dp[i][1][1])%mod;
        }
        for(int i=1;i<=n;i++)dp[i][1][0]=dp[i][0][1]=dp[i][1][1]=0;
        f[0][0][0][0]=1;
        for(int i=1;i<=n;i++){
            if(i>=1)f[i][1][0][0]=1ll*(f[i-1][1][0][0]+f[i-1][0][0][0])%mod*inv3%mod;
            if(i>=3)f[i][0][1][0]=1ll*(f[i-3][0][1][0]+f[i-3][0][0][0])%mod*inv3%mod;
            if(i>=3)f[i][1][1][0]=1ll*(1ll*f[i-1][0][1][0]+f[i-1][1][1][0]+f[i-3][1][0][0]+f[i-3][1][1][0])%mod*inv3%mod;
            if(i>=4)f[i][0][0][1]=1ll*(f[i-4][0][0][1]+f[i-4][0][0][0])%mod*inv3%mod;
            if(i>=4)f[i][1][0][1]=1ll*(1ll*f[i-1][0][0][1]+f[i-1][1][0][1]+f[i-4][1][0][0]+f[i-4][1][0][1])%mod*inv3%mod;
            if(i>=4)f[i][0][1][1]=1ll*(1ll*f[i-3][0][0][1]+f[i-3][0][1][1]+f[i-4][0][1][0]+f[i-4][0][1][1])%mod*inv3%mod;
            if(i>=4)f[i][1][1][1]=1ll*(1ll*f[i-1][0][1][1]+f[i-1][1][1][1]+f[i-3][1][0][1]+f[i-3][1][1][1]+f[i-4][1][1][0]+f[i-4][1][1][1])%mod*inv3%mod;
            ans=(ans+f[i][1][1][1])%mod;
        }
        for(int i=1;i<=n;i++)f[i][1][0][0]=f[i][0][1][0]=f[i][1][1][0]=f[i][0][0][1]=f[i][1][0][1]=f[i][0][1][1]=f[i][1][1][1]=0;
        printf("%lld\n",ans);
    }
    return 0;
}

如果你容斥的话那矩阵会很小，可以手推出来。但是如果你暴力 dp 加维还像我这样比较不带脑子的写的话，那么最后一个矩阵是 \(25\times 25\) 的。然后我当时看到就直接润了。

蚌埠了，贺了一份 Delov 的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int mod=998244353,inv2=(mod+1)>>1,inv3=(mod+1)/3;
long long n;
int ans;
int qpow(int a,long long b){
    int ans=1;
    while(b){
        if(b&1)ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b>>=1;
    }
    return ans;
}
struct node{
    int n,a[6][6];
    node(){memset(a,0,sizeof(a));n=0;}
    void clear(){memset(a,0,sizeof(a));n=0;}
    node operator*(const node&s)const{
        node ret;ret.n=n;
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++){
            ret.a[i][j]=(ret.a[i][j]+1ll*a[i][k]*s.a[k][j])%mod;
        }
        return ret;
    }
};
node qpow(node a,long long b){
    node ans;ans.n=a.n;
    for(int i=1;i<=ans.n;i++)ans.a[i][i]=1;
    while(b){
        if(b&1)ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int calc(int x,int n){
    return 1ll*x*(1-qpow(x,n)+mod)%mod*qpow(1-x+mod,mod-2)%mod;
}
signed main(){
    int tim;scanf("%lld",&tim);
    while(tim--){
        scanf("%lld",&n);ans=0;
        ans=(ans+inv2+1)%mod;
        ans=(ans+1ll*(1-qpow(inv3,n)+mod)%mod*inv2)%mod;
        ans=(ans-1ll*(1-qpow(inv3,n-1>>1)+mod)%mod*inv2%mod+mod)%mod;
        ans=(ans+2ll*(1-qpow(2ll*inv3%mod,n-1>>1)+mod))%mod;
        node a,b;a.n=b.n=3;
        a.a[1][1]=1;
        b.a[1][1]=b.a[2][1]=b.a[1][3]=b.a[2][3]=inv3;
        b.a[1][2]=b.a[3][3]=1;
        a=a*qpow(b,n);
        ans=(ans+a.a[1][3])%mod;
        ans=(ans-calc(inv3,n>>1)+mod)%mod;
        ans=(ans-calc(inv3,n)+mod)%mod;
        a.clear();b.clear();a.n=b.n=4;
        a.a[1][1]=1;
        b.a[1][1]=b.a[1][4]=b.a[3][1]=b.a[3][4]=inv3;
        b.a[1][2]=b.a[2][3]=b.a[4][4]=1;
        a=a*qpow(b,n);
        ans=(ans+a.a[1][4])%mod;
        ans=(ans-calc(inv3,n)+mod)%mod;
        ans=(ans-calc(inv3,n/3)+mod)%mod;
        a.clear();b.clear();a.n=b.n=5;
        a.a[1][1]=1;
        b.a[1][1]=b.a[1][5]=b.a[3][1]=b.a[4][1]=b.a[3][5]=b.a[4][5]=inv3;
        b.a[1][2]=b.a[2][3]=b.a[3][4]=b.a[5][5]=1;
        a=a*qpow(b,n);ans=(ans+a.a[1][5])%mod;
        a.clear();b.clear();a.n=b.n=5;
        a.a[1][1]=1;
        b.a[1][1]=b.a[1][5]=b.a[3][1]=b.a[3][5]=inv3;
        b.a[1][2]=b.a[2][3]=b.a[3][4]=b.a[5][5]=1;
        a=a*qpow(b,n);ans=(ans-a.a[1][5]+mod)%mod;
        a.clear();b.clear();a.n=b.n=5;
        a.a[1][1]=1;
        b.a[1][1]=b.a[1][5]=b.a[4][1]=b.a[4][5]=inv3;
        b.a[1][2]=b.a[2][3]=b.a[3][4]=b.a[5][5]=1;
        a=a*qpow(b,n);ans=(ans-a.a[1][5]+mod)%mod;
        a.clear();b.clear();a.n=b.n=5;
        a.a[1][1]=1;
        b.a[3][1]=b.a[4][1]=b.a[3][5]=b.a[4][5]=inv3;
        b.a[1][2]=b.a[2][3]=b.a[3][4]=b.a[5][5]=1;
        a=a*qpow(b,n);ans=(ans-a.a[1][5]+mod)%mod;
        ans=(ans+calc(inv3,n))%mod;
        ans=(ans+calc(inv3,n/3))%mod;
        ans=(ans+calc(inv3,n/4))%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

标签：省选,题解,inv3,int,1ll,欢乐,ans,dp,mod
From： https://www.cnblogs.com/gtm1514/p/17273910.html

相关文章

  • php 浮点数转int精度丢失问题解决办法
    方案一：先将浮点金额strval后再转int。（推荐）$param['order_price']=intval(strval($param['order_price']*100)); 方案二： echoround(19.99*100); 这种方案出来是......
  • P4156 [WC2016]论战捆竹竿 题解
    题目链接题意描述给定一个字符串\(S\)，你初始拥有一个空串\(T\)，每次可以选择这个字符串的一个Border，去掉它后接在\(T\)的后面，操作后\(S\)不变，给出一个上限\(w\)，求......
  • CF1295E Permutation Separation 题解 线段树优化dp
    题目链接：https://codeforces.com/problemset/problem/1295/E题目大意：将排列\(p_1,p_2,\ldots,p_n\)先分成\(p_1,\ldots,p_k\)与\(p_{k+1},\ldots,p_n\)两个......
  • 【题解】[HEOI2013]SAO
    题目分析：考虑这是一个树形图，所以就先直接当作树来做。这个题其实就是让我们求解有多少种拓扑序而且题目中边方向的限制其实就是在限制拓扑序的前后，而一般这种题在设计\(......
  • 【题解】Codeforces Round 861（CF1808）A - E1
    我忘记了今天有阳间CF，所以就开打的很晚，所以只是说一下做法，代码实现....还是算了吧。但是我也看了，我的思路其他的人都有写，所以这个做法正确性没问题。A.LuckyNumbers题......
  • 2023省选联考复习
    字符串\(KMP\)\(Z\)函数字符串哈希\(Manacher\)\(PAM\)回文自动机\(ACAM\)\(AC\)自动机\(SAM\)后缀自动机*\(SA\)后缀数组*\(ST\)后缀树......
  • CF1009F 题解
    一、题目描述：给定一棵以 1 为根，n 个节点的树。设 d(u,x) 为 u的子树中到 u 距离为 x 的节点数。对于每个点，求一个最小的 k，使得 d(u,k) 最大。 二、......
  • CentOS7中远程连接数据库连不上的问题解决方法
      当远程连接数据库连接不起来时：可能原因：1.检查网络防火墙或其他安全设置是否阻止了连接  2.mysql服务是否启动，查看systemctlstatusmysql3.是否提前授权：......
  • ABC291题解(D-G)
    ABC291D-FlipCardsSolution:考虑DP，定义状态\(F_{i,0}\)为第\(i\)张卡片正面朝上的方案数，\(F_{i,1}\)为第\(i\)张卡片背面朝上的方案数，每次check是否相同然后转移即可......
  • 使用SQLALCHEMY 出现warning的问题解决
    运行程序时出现错误：UserWarning:NeitherSQLALCHEMY_DATABASE_URInorSQLALCHEMY_BINDSisset.DefaultingSQLALCHEMY_DATABASE_URIto"sqlite:///:memory:".'Neithe......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99