CF772D题解
什么阴间十进制状压
题意:给定 $ n $ 数字,求定义函数 $ G(x) $ 能够表示 满足“十进制按位与为 $ x $”的集合的平方和之和乘上 \(x\),求 \(\bigoplus _{i=0}^{999999}G(i)\)。
这个题很明显干的事情就是让我们对每个数求出一车集合,然后将这一车集合用奇怪的方式加密输出。
当你在求恰好的时候,先想想如何求包含,因为恰好特别难求。
包含不就是个十进制的超集求和?
枚举哪一位,内层再套一个枚举每一个下标,如果这个下标的这一位是 \(9\) 就不转移,否则就做一个后缀和。
然后已经得到包含了,如何得到恰好?
先不想十进制,先来想想二进制干了些什么。
二进制似乎就是做了类似 \(a[n][m]=s[n][m]-s[n-1][m]-s[n][m-1]+s[n-1][m-1]\) 的事情?
也就是差分,所以再差分回去。
不过要注意最前面的后缀和是合并集合意义上的后缀和,后面的差分仅仅是对平方和的差分。
为什么是这样的?
假设这个数组是 \(f[S]\),那么 \(f[S]\) 包含的是一车平方和之和,平方和之间没有任何关系,当然可以做一个差分把多的部分扔掉。
那么问题来了,如何维护平方和?
\]
所以维护一个 $ 0 $ 次和与一个一次和,再维护一个二次和。可以做到 \(O(6 \times 10^6 \times 2^2)\)。
一次和用类似的推柿子即可。
不过理论上来说这玩意儿实际上是低次多项式,所以可以使用将多项式转化为下降幂多项式的 trick,\(O(2)\) 合并两个下降幂多项式,最后 \(O(2)\) 得到答案,复杂度是 \(O(6 \times 10^6 \times 2+10^6 \times 2+2^2)\)。不过没有啥意义
注意一下这题的输出有点儿奇怪,是取模之后乘上一个数再异或,而不是乘上一个数之后取模再异或
#include<cstdio>
#include<cctype>
typedef unsigned ui;
const ui M=1000005,mod=1e9+7,pw10[]={1,1,10,100,1000,10000,100000};
ui n,B[M];char buf[M*7],*p=buf;
inline ui read(){
ui n(0);char s;while(!isdigit(s=*p++));while(n=n*10+(s&15),isdigit(s=*p++));return n;
}
struct data{
ui s0,s1,s2;
data(const ui&s0=1,const ui&s1=0,const ui&s2=0):s0(s0),s1(s1),s2(s2){}
inline data operator*(const data&it)const{
return data(1ull*s0*it.s0%mod,(1ull*s1*it.s0+1ull*s0*it.s1)%mod,(1ull*s2*it.s0+2ull*s1*it.s1+1ull*s0*it.s2)%mod);
}
}f[M];
signed main(){
ui i,j,k,x;unsigned long long ans(0);fread(buf,1,sizeof buf,stdin);n=read();
for(i=1;i<=n;++i)x=read(),f[x]=f[x]*data(2,x,1ull*x*x%mod);
for(i=1;i<=6;++i)for(j=999999;~j;--j)if(j/pw10[i]%pw10[2]^9)f[j]=f[j]*f[j+pw10[i]];
for(i=0;i^1000000;++i)B[i]=f[i].s2;
for(i=1;i<=6;++i)for(j=0;j^1000000;++j)if(j/pw10[i]%pw10[2]^9)B[j]=(B[j]+mod-B[j+pw10[i]])%mod;
for(i=0;i^1000000;++i)ans^=1ull*i*(B[i]%mod);printf("%llu",ans);
}
最新文章
- php实现设计模式之 访问者模式
- mysql数据库中如何修改已建好的表中的【列名】【列的属性】
- mysql 二进制文件增量备份
- 第三方开源水面波浪波形view:WaveView
- 高性能WEB开发(6) - web性能測试工具推荐
- mock server相关解决方案
- MongoDB的save 和insert函数的区别
- Javascript debugger come accross error
- iOS 测试三方 KIF 的那些事
- Vijos P1784 数字统计【模拟】
- CSS预处理器之Less详解
- .Net Core SDK 命令介绍
- Spark安装部署| 运行模式
- Spring Boot - 修改Tomcat默认的8080端口
- C++.Linux下redis编程:error while loading shared libraries: libhiredis.so.0.13
- 23.Mysql应用优化
- canvas画的时钟
- Android xUtils3源代码解析之网络模块
- 【Python编程:从入门到实践】chapter4 操作列表
- Java线程的阻塞
热门文章
- Redis 学习笔记(六)Redis 如何实现消息队列
- Docker名词解释
- 如何在Kubernetes 里添加自定义的 API 对象(一)
- Solution -「JOISC 2021」古老的机器
- 日行一算(Table-文字输出)
- 轻量级DI框架Guice使用详解
- spring的事务是如何回滚的、事务传播?
- Dell服务器配置RAID1+RAID0磁盘阵列
- 【C# IO 操作】使用StringWriter和StringReader的好处
- [源码解析] NVIDIA HugeCTR,GPU 版本参数服务器---(8) ---Distributed Hash之后向传播