题意

给出一个长为200的01序列,判断是否在前1e9个莫比乌斯*值中。(这里的莫比乌斯值加了绝对值)

分析

意到因为4的倍数一定是0,9的倍数一定是0……169的倍数一定是0。那么我们可以对4,9,25,49,121,169这6个200以内这质数平方进行考虑。

我们可以枚举起点位置 $x$ 对这6个数的模数,然后用CRT求出 $x$。对每个起点位置,暴力对比即可。不可能存在所有的mu值,只能单个求。

由于0的个数介于65~95,所以符合条件的起点位置并不多,因此不会超时。

#include <bits/stdc++.h>
using namespace std; typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll up = 1e9;
const int N = 5e4 + ; int prime[N];
bool notprime[N];
void getprime()
{
for (int i = ; i < N; i++) {
if(!notprime[i]) prime[++prime[]] = i;
for (int j = ; j <= prime[] && i * prime[j] < N; j++)
{
notprime[i * prime[j]] = ;
if(i%prime[j]==) break;
}
}
} int mu(int x) { //求单个mu值
for (int i = ; i <= prime[] && prime[i] * prime[i] <= x; i++) {
if(x%(prime[i]*prime[i]) == ) return ;
if(x%prime[i] == ) x/=prime[i];
}
return ;
} ll exgcd(ll a,ll b,ll &x, ll &y) {
ll g = a;
if(b==) x=,y=; else g=exgcd(b,a%b,y,x),y-=x*(a/b);
return g;
} ll inv(ll a,ll m) {
ll x, y;
ll d = exgcd(a, m, x, y);
return (d == ) ? (x % m + m) % m : -;
} int ti[], m[] = {, , , , , }, a[];
int M; void CRT() {
M = ;
for(int i = ; i < ; i ++) M = M*m[i];
for(int i = ; i < ; i++) {
int Mi = M/m[i];
ti[i] = 1LL*inv(Mi, m[i])*Mi%M;
}
} string s,t; int check(int v, int r) {
while(v < ) {
if(s[v] == '') return ;
v += r;
}
return ;
} int ok(int x) {
for (int i = ; i < ; i++)
if(mu(i+x) != s[i]-'') return ;
return ;
} int ans = inf; void dfs(int x) {
if(x == ) {
int v = ;
for(int i = ; i < ; i++) v = (v + 1LL*ti[i]*a[i]%M)%M; //v为CRT的值
if(v == ) v = M;
while(v+ <= up && v < ans) {
if(ok(v)) ans = v;
v = v + M;
}
return;
}
for(int i = ; i < m[x]; i++) { //枚举余数a[i]
if(check(i, m[x])) {
a[x] = ( m[x] - i );
dfs(x+);
}
}
} int main(){
getprime();
CRT();
for(int i = ; i < ; i++) {cin >> t, s = s + t;}
int num = ;
for(int i = ; i < s.size(); i++)
if(s[i] == '') num++;
if(num < || num > ) //0的个数在一个范围内
cout << - << endl;
else {
dfs();
if(ans == inf)
cout << - << endl;
else
cout << ans << endl;
}
return ;
}

参考链接:

1. https://blog.csdn.net/BUAA_Alchemist/article/details/86652706

2. https://blog.csdn.net/a1214034447/article/details/86373308

3. https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40622831

最新文章

  1. 查看Validate Subscription 的结果
  2. 【转载】Web移动端Fixed布局的解决方案
  3. arduino 入手
  4. IOS 项目 小说 1
  5. 提高Asp.Net应用程序性能的十大方法(译感)
  6. C结构体之位域(位段)
  7. 用 hugo 和 netlify 搭建blog【转】
  8. MATLAB常用快捷键命令总结
  9. C#【结对编程作业】小学数学习题助手
  10. 用图来教你怎样用Photoshop蓝底转换红底
  11. Numpy:ndarray数据类型和运算
  12. 解释一下核主成分分析(Kernel Principal Component Analysis, KPCA)的公式推导过程(转载)
  13. mysql-5.7.18解压版启动mysql服务
  14. WEBLOGIC的安装、配置和启动
  15. Mac环境下配置tomcat的步骤详解
  16. 解题:SCOI 2010 序列操作
  17. lua——string之string.gsub
  18. /etc/sysctl.conf
  19. 在linux下编译线程程序undefined reference to `pthread_create&#39;
  20. Spring实战之处理自动装配的歧义性

热门文章

  1. IntelliJ IDEA最新版2019年注册码,可激活至2099年 激活 破解
  2. Visual Studio 调试系列12 远程调试部署在远程计算机IIS上的ASP.NET应用程序
  3. Azure DevOps Server 经验分享(国内重型工程公司)
  4. python 根据文件的编码格式读取文件
  5. (98)address already in use: ah00072: make_sock: could not bind to address 0.0.0.0:80
  6. sqlyog管理关系型数据库mysql数据库之sqlyog的安装管理
  7. linux搜索log文件的内容
  8. 项目Gradle版本从4.4升级到4.6
  9. 【java】java反射获取属性和属性值,java反射设置属性和属性值
  10. C# WebBrowser控件 下载文件不弹下载提示框的办法