中国剩余定理。

可以手动模拟一下每一次开始的人的编号和结束的人的编号。

每次删掉一个人,对剩下的人重新编号。

这样一次模拟下来,可以得到n个方程

形如:(u[i]+k)%(n-i+1)=v[i]

化简一下就是:k%(n-i+1)=v[i]-u[i]%(n-i+1)

接下来就是求解最小的k,满足所有式子

中国剩余定理板子一套就AC了......

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std; typedef long long LL;
const int maxn = ;
int n, T;
int s[maxn], flag[maxn], tmp[maxn]; int u[], v[];
LL a[maxn], b[maxn]; void ls()
{
int cnt = ;
for (int i = ; i <= n; i++)
{
if (flag[i] == )
tmp[cnt++] = i;
}
} int Find(int a)
{
for (int i = a; i <= n; i++)
if (flag[i] == ) return i;
for (int i = ; i <= a; i++)
if (flag[i] == ) return i;
} int f2(int a)
{
for (int i = ;; i++)
if (tmp[i] == a) return i;
} void egcd(LL a, LL b, LL&d, LL&x, LL&y)
{
if (!b) { d = a, x = , y = ; }
else
{
egcd(b, a%b, d, y, x);
y -= x*(a / b);
}
} LL lmes() {
LL M = a[], R = b[], x, y, d;
for (int i = ; i <= n; i++) {
egcd(M, a[i], d, x, y);
if ((b[i] - R) % d) return -;
x = (b[i] - R) / d*x % (a[i] / d);
R += x*M;
M = M / d*a[i];
R %= M;
}
return (R + M) % M ? (R + M) % M : M;
} void exgcd(LL a, LL b, LL &d, LL &x, LL &y)
{
if (b == )
d = a, x = , y = ;
else
{
exgcd(b, a%b, d, y, x);
y -= x * (a / b);
}
} LL china(LL n, LL m[], LL a[])
{
LL aa = a[];
LL mm = m[];
for (int i = ; i<n; i++)
{
LL sub = (a[i] - aa);
LL d, x, y;
exgcd(mm, m[i], d, x, y);
if (sub % d) return -; LL new_m = m[i] / d;
new_m = (sub / d*x%new_m + new_m) % new_m;
aa = mm*new_m + aa;
mm = mm*m[i] / d;
}
aa = (aa + mm) % mm;
return aa ? aa : mm;
} int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
int ai; scanf("%d", &ai);
s[ai] = i;
}
memset(flag, , sizeof flag); u[] = , v[] = s[];
if (v[] == n) v[] = ; flag[s[]] = ; for (int i = ; i <= n; i++)
{
int st, en;
ls();
st = Find(s[i - ]), st = f2(st), st = st - ;
if (st == -) st = n - i;
en = f2(s[i]), u[i] = st;
v[i] = en; if (v[i] == n - i+) v[i] = ;
flag[s[i]] = ;
}
/*
for (int i = 1; i <= n; i++)
printf("%d %d\n", u[i], v[i]);
*/ //接下来就是求解最小的k,满足所有式子
//k%(n-i+1)=v[i]-u[i]%(n-i+1) for (int i = ; i <= n; i++)
{
a[i] = (LL)(n - i + );
b[i] = (LL)(v[i] - u[i] % (n - i + ));
}
LL k = china(n, a + , b + );
if (k == -) printf("Creation August is a SB!\n");
else printf("%lld\n", k);
}
return ;
}

最新文章

  1. [bzoj3673][可持久化并查集 by zky] (rope(可持久化数组)+并查集=可持久化并查集)
  2. chrome浏览器调试typescript
  3. php复习第一章—1.1php 简介
  4. fir.im Weekly - Stanford 的 Swift 课程来了
  5. z/os上的tar和gzip
  6. 使用mongo-java-driver3.0.2.jar和mongodb3.0在java代码中的用户验证4
  7. git(4)如何在windows上安装git
  8. 文件和目录之设置用户ID和设置组ID
  9. AndroidUI组件之ActionBar--基于下拉的导航方式
  10. 《Programming WPF》翻译 第7章 5.可视化层编程
  11. 【Unity3d】【项目学习心得】从资源server下载资源(一)
  12. bug:翻页
  13. MkDocs项目文档生成器
  14. teachable-machine:探索机器学习如何工作,浏览器中实时浏览
  15. 从壹开始前后端分离 [ Vue2.0+.NET Core2.1] 十四 ║ VUE 计划书 &amp; 我的前后端开发简史
  16. Groovy语言学习--语法基础(2)
  17. Ansible系列(四):playbook应用和roles自动化批量安装示例
  18. Java基础再复习(继承、多态、方法内部类**、HashMap用法**、参数传递**)
  19. Alberta family&#39;s QR code is world&#39;s largest corn maze
  20. 【JAVAWEB学习笔记】19_事务概述、操作、特性和隔离级别

热门文章

  1. phpstorm设置代码块快捷方式
  2. IOS代码收集
  3. 回顾PMP考试
  4. webpack3整理(第三节/满三节)------(base.config文件解释)
  5. IntelliJ IDEA openfire 使用IntelliJ IDEA 部署OPENFIRE 服务端
  6. CortexA7工业级迅为-iMX6UL开发板硬件和资料介绍
  7. mysql查询-从表1中查询出来的结果重新插入到表1
  8. 前端什么是BFC
  9. day24-2 单例模式
  10. Dreamoon and MRT