首页 > 其他分享 >2024牛客暑期多校训练营2

2024牛客暑期多校训练营2

时间:2024-07-27 19:06:53浏览次数:16  
标签:状态 state int 多校 2024 牛客 因子 序列 1000

G The Set of Squares

思路:

对于一个序列内的所有数的乘积可以分解为p1k1p2k2...pnkn,(p为质数)此时只有当k都为偶数时,这个序列数的乘积才为完全平方数

当在两个序列当中,所有k为奇数时对应的质数p都相同,说明这两个序列合并可以构成完全平方数

那么可以以ki的奇偶来表示某个质数的状态,k为奇数状态为1,为偶数状态为0。比如31的状态为1,32的状态为0

那么p1k1p2k2...pnkn的状态就可以以二进制(10101000...)的形式表示

只有当两个串的每一位都相等时才能合并构成完全平方数

那么f[i]表示为序列的乘积质因子分解后的状态为i的贡献和

最后的答案即为f[0]

这里二进制表示状态的位数是有限的,可以对s根据质因子进行分类

对于一个数,最多只会存在一个质因子大于√1000,且剩下的质因子都小于√1000

可以发现小于√1000的质因子只有{2, 3, 5, 7, 11, 13,17, 19, 23, 29, 31 }共11个

那么对于一个乘积为完全平方的序列来说出现的质因子种类数最多为12,这个范围就可以用二进制表示了

可以把出现质因子大于√1000的数按最大质因子分类,质因子都小于√1000的属于一类

在分类时,求出每个数的状态和贡献(此时的贡献里不包括状态里所有k为奇数的p中,多出的那一个p,比如33的状态为1,贡献为3(√32带来的贡献,还多出一个3存在状态里)

所有数的状态和贡献求完后,接着就要一个一个的选数,同时转换序列状态和更新贡献

枚举选完上一个数的所有序列状态i,当前数的状态为state,将当前数加入序列后的状态转移为:now = i ^ state,贡献更新为val[i] + (i 和 state中都为1的个数,即 i & state中1的个数) 

对于最大质因子大于√1000的那类数,用的都是二进制中同一位来表示,所以每次处理完后都需要清空(因为大于√1000的质因子只会乘上自己来构成完全平方数,且每一类数的最大质因子不相同)

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
const int N = 1e6 + 5, mod = 998244353, Mod = 1e9 + 7, inf = 1e18;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int dg[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};

void solve() {
    int n;
    cin >> n;
    map<int, vector<PII> > mp;
    for (int i = 1; i <= n; ++i) {
        int s;
        cin >> s;
        int state = 0, val = 1;
        for (int j = 0; j < 11; ++j) {
            if (s % dg[j] == 0) {
                while (s % dg[j] == 0) {
                    state ^= (1 << j);
                    if ((state & (1 << j)) == 0) {
                        val = val * dg[j] % Mod;
                    }
                    s /= dg[j];
                }

            }
        }
        mp[s].push_back({state, val});
    }
    vector<int> f(1 << 12);
    f[0] = 1;
    for (auto [p, vec]:mp) {
        for (auto [state, val]:vec) {
            vector<int> ff = f;
            if (p != 1) {
                state |= (1 << 11);
            }
            for (int i = 0; i < (1 << 12); ++i) {
                int now = state ^ i;
                int ans = f[i] * val % Mod;
                int ch = state & i;
                for (int j = 0; j < 11; ++j) {
                    if ((ch >> j) & 1) ans = ans * dg[j] % Mod;
                }
                if ((ch >> 11) & 1) ans = ans * p % Mod;
                ff[now] = (ff[now] + ans) % Mod;
            }
            f = ff;
        }
        for (int i = 1 << 11; i < (1 << 12); ++i) f[i] = 0;
    }
    cout << f[0] - 1;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

 

标签:状态,state,int,多校,2024,牛客,因子,序列,1000
From: https://www.cnblogs.com/bible-/p/18327171

相关文章

  • 2024/07/27 每日一题
    LeetCode3106满足距离约束且字典序最小的字符串classSolution:defgetSmallestString(self,s:str,k:int)->str:ans=list(s);res=ord('a')fori,xinenumerate(map(ord,ans)):cnt=min(x-res,res+26-x)......
  • 算法训练 2024.7.27 17:25
    目录1.两数之和2.反转链表3.是否为有效的括号4.最长公共前缀5.合并两个有序数组6.岛屿的个数7.最小路径和8.三数之和9.计数质数10.字符串转换整数(atoi)1.两数之和题目:给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整......
  • Python数据预处理+正态性检验+异常值处理+Q-Q图-K-S检验+相关性分析(2024MathorCup A题
    #数据预处理#正态性检验、Q-Q图、箱线图、直方图、相关性分析#Q-Q图importnumpyasnpimportpandasaspdimportmatplotlib.pyplotaspltfromscipy.statsimportnormfromscipy.statsimportprobplota=pd.read_excel('附件1:小区基本信息.xlsx',engine='openpyxl'......
  • 2024暑假第四周总结
    数组容器,可以用来存储同种数据类型的多个值需要结合隐式转换考虑容器的类型和存储数据的类型保持一致数组的定义:格式一:数据类型[]数组名int[]array格式二:数据类型数组名[]intarray[]数组初始化:在内存中,为数组容器开辟空间,并将数据存入容器中的过程数组静态初......
  • 2024.7.22至2024.7.27周总结
    本周学习任务清单数据结构:树链剖分。解题思路:CDQ分治,整体二分。数论:费马小定理,素数筛法,欧拉定理,逆元,拓展欧几里得算法,中国剩余定理,Miller_Rabin素数检测,PollarRho分解质因数算法。多项式和生成函数:拉格朗日插值法,普通生成函数。线性代数:向量,线性组合,线性变换,线性,矩阵,行列......
  • 2024暑假集训测试13
    前言比赛链接。从来没见过交互题,T1狂CE不止心态炸了,后面的题也没打好,T2、T3简单题都不会了,所以为啥T4又放黑题。T1大众点评原题:AT_joisc2014_d。难点主要在交互,赛时琢磨了半场比赛终于搞明白是啥玩意儿了,可以将给定库当成压缩的一部分代码,可以调用里面的函数,输入......
  • 怎么判断电脑屏幕被监控?电脑被监控可以看到什么?丨2024超强科普!
    各位同仁,是不是正在怀疑自己的电脑被监控了?那么又该怎么盘点自己的电脑是不是正在被监控,假如真的被监控,老板又会看到什么内容呢?别急,且听我慢慢道来!一、电脑被监控的表现黑屏闪烁当电脑被监控时,屏幕可能会出现短暂的黑屏或频繁闪烁。这种情况多出现在电脑启动或打开特定程......
  • P2024 [NOI2001] 食物链
    原题链接题解关系具有矢量特性,因此可以带权并查集维护code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intfa[50006];intval[50006];intfinds(intnow){if(now==fa[now])returnnow;inttem=fa[now];fa[now]=finds(fa[now])......
  • (超详细)备赛笔记2024年全国职业院校(中职组)技能大赛(ZZ052大数据应用与服务)第二套试题
    2024年职业院校中职组ZZ052大数据应用与服务赛项赛题第02套【子任务一:基础环境准备】模块一:平台搭建与运维(一)任务一:大数据平台搭建1.子任务一:基础环境准备(1)对三台环境更新主机名,配置hosts文件,以node01作为时钟源并进行时间同步;#分别在不同主机上面执......
  • 随笔之甲辰年(2024)
    前言之所以用天干地支,大概是因为最近追《一人之下》,里面提到了“甲申之乱”。自己又年近不惑,突然感慨六十年一个甲子,俗话说“三十年河东,三十年河西”,也刚好六十年。估摸着我大概也许六十岁的时候,也会喜欢上这种颇具中国传统色彩的叫法,仅此而已辛未月(7月)壬辰日(27日)农历六月......