首页 > 其他分享 >CW初中-C106D

CW初中-C106D

时间:2023-12-07 20:57:16浏览次数:30  
标签:11 10 leq pa 初中 mod C106D CW equiv

稍微重复一下题意,有 \(n\) 个数 \(a_i\),将其以一种顺序串联成一个“大数”,使这个数对 \(11\) 取模的结果为 \(0\),求一共有多少个不同的顺序?方案数对 \(998244353\) 取模。另外,相同的数若在 \(a\) 数组中多次出现,则视为不同的数。

\(0 \leq a_i \leq 10^9, 0 < n \leq 2000\)

首先许多同学会首先想到 \(11\) 倍数的性质:“两头一拉,中间相加”。但是信息学竞赛生的直觉告诉我们若将此题化为这样的问题只是在使题目变复杂。

所以我们做题的一个首要步骤是将题目化简或变得易懂、更易思考、更易入手、更易实现。

性质:

设:

\(10^pa \equiv b \; (mod\;11)\),其中 \(b\) 满足 \(0 \leq b < 11\)。

\[\because 10^pa \equiv b \; (\!\!\!\!\!\!\mod \; 11) \]

\[\therefore (10 - 11) ^ pa \equiv b \; (\!\!\!\!\!\!\mod \; 11) \]

\[\therefore (- 1) ^ pa \equiv b \; (\!\!\!\!\!\!\mod\;11) \]

\[\therefore b = \begin{cases} a & p \; is \; odd \\ 11 - a & p \; is \; even \\ \end{cases} \]

结论:

设:

\( e_i = \begin{cases} 1 & ((\log_{10}{a_i}) + 1) \; is \; odd \\ -1 & ((\log_{10}{a_i}) + 1) \; is \; even \\ \end{cases} \)

假设有一种已知顺序 \(b_1,b_2,b_3...b_n\)。

由上述性质得:

若 \(b_1,b_2,b_3...b_n\) 为一种合法的顺序,则有:

\[\sum_{i=1}^{n}(a_{b_i} \prod_{j=1}^{i-1}(e_{b_j})) \equiv 0 \;\;\; (\!\!\!\!\!\!\mod 11) \]

解释一下,由上述性质可知一个 \(a_i\) 对总和的影响取决于它后面的位数,若 \(a_i\) 向低位的位数为奇数,则将总和减去 \(a_i\),否则将总和加上 \(a_i\)。

剩下的求方案数就是 DP 的事了,这种式子下的转移就十分地简单,而且有多种转移方式(我的方法比较蠢)。如果想不到就问问教练或身边的其他同学,如果实在不清楚,也可以在评论区留言,我看情况把我的 DP 方程放上来。当然有自己的转移方法的也可以在评论区提出。

给一个提示,可以将 \(e_i\) 分正负分别讨论DP方程,然后再用乘法原理之类的组合起来。

因为我累了,所以这篇博客就到这里吧。

标签:11,10,leq,pa,初中,mod,C106D,CW,equiv
From: https://www.cnblogs.com/imcaigou/p/17883915.html

相关文章

  • AcWing 802. 区间和
    题面:假定有一个无限长的数轴,数轴上每个坐标上的数都是\(0\)。现在,我们首先进行\(n\)次操作,每次操作将某一位置\(x\)上的数加\(c\)。接下来,进行\(m\)次询问,每个询问包含两个整数\(l\)和\(r\),求出在区间\([l,r]\)之间的所有数的和。原题链接:802.区间和-AcW......
  • 59AcWing 840. 模拟散列表
    点击查看代码#include<iostream>#include<cstring>usingnamespacestd;constintN=200003,null=0x3f3f3f3f;inth[N];intfind(intx){intk=(x%N+N)%N;//索引while(h[k]!=null&&h[k]!=x){k++;if(k==N)k=0;//重新搜索......
  • 初中英语优秀范文100篇-019A Meaningful Activity-一次有意义的活动
    PDF格式公众号回复关键字:SHCZFW019记忆树1I'malwayshappywhenImemorizethatmeaningfulactivity.翻译我总是很高兴,当我记住那些有意义的活动。简化记忆高兴句子结构这个句子的结构如下:主语:I(我)谓语:am(是)表语:alwayshappy(总是快乐)状语从句:whenIm......
  • CWOI 字符串专题
    A-IndieAlbum考虑离线,对询问串跑AC自动机,建出fail树。再把题目中那个版本继承关系建成一棵树,在这棵树上dfs,进入一个点的时候在fail树上单点加,走的时候减掉,维护子树求和即可。点击查看代码#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;const......
  • Acwing 5367. 不合群数
    题面:如果一个正整数无法被 \([2,a]\) 范围内的任何整数整除,则称其为不合群数。请你计算并输出 \([2,b]\) 范围内的最大不合群数。提示:\(10\) 亿内的最大质数是 \(999999937\),且相邻质数之间的差值均不超过 \(300\)原题链接:5367.不合群数-AcWing根据给出的提示判......
  • 初中英语优秀范文100篇-018My Summer Holiday-我的暑假
    PDF格式公众号回复关键字:SHCZFW018记忆树1MyfamilyandIwenttoHongKongtospendourholidaythissummer.翻译我和我的家人这个夏天去了香港度假简化记忆香港句子结构这个句子的结构可以分为以下几部分:主语:MyfamilyandI(我和我的家人)谓语动词:went(去)宾......
  • cw 字符串专题
    KMP和AC自动机都只会背板子怎么办啊/kk。模板AC自动机不会,但我会背板子。for(inti=0;i<26;i++)ch[0][i]=1;queue<int>q;q.push(1);while(!q.empty()){intu=q.front();q.pop();for(inti=0;i<26;i++)if(!ch[u][i])ch[u][i]=ch[fail[u]][i];......
  • 初中英语优秀范文100篇-017A Special Farmily Member-一位特殊的家庭成员
    PDF格式公众号回复关键字:SHCZFW017记忆树1Ben,acutedog,isaspecialmemberinmyfamily.翻译本,一只可爱的狗狗,是我家的特别成员。简化记忆狗狗句子结构这个句子的结构可以进行详细分析如下:主语:Ben,acutedog(Ben,一只可爱的狗)谓语动词:is(是)宾语:aspecial......
  • AcWing 1205. 买不到的数目
    题面:水果糖被包成\(n\)颗一包和\(m\)颗一包的两种,用这两种包装来组合,不能拆包卖。在\(4\)颗一包和\(7\)颗一包的情况下,最大不能买到的数量是\(17\)。本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。原题链接:1205.买不到的数目-AcWing数论:组合......
  • ACwing342. 道路与航线
    这道题是把拓扑排序和迪杰斯特拉交叉进行。#include<iostream>#include<stdio.h>#include<algorithm>#include<cstring>#include<queue>#include<vector>usingnamespacestd;typedefpair<int,int>PII;constintN=25005,M=50......