2333333333333333333333333333333333333333333333333333333333333333333333333333333

我居然拉低了2%的正确率

以下是O(c^3)的暴力做法（含几处优化），95%的测试点Accept（除了第四个变态的测试点）

基本思路：枚举x,a,b<c，然后逐项验证，此时间复杂度O(n*c^3)

优化一：经过Excel实验或理论分析，发现random()函数具有周期性，并且c-1为其周期，所以只要验证前min(2*c,n-1)项即可。
时间复杂度优化为O(c^4)

优化二：经过Excel实验或理论分析，在n>c+1时，发现当x与a确定时，b最多只有一个符合要求。
时间复杂度优化为O(c^3)

优化三：当i>c时，任意数字mod c mod i==该数字mod c，即不需mod i。
提高10%~20%左右效率。

#include<cstdio>
#include<cctype>

const int maxn=1001000;
long int n,a,b,c,x,f,ans[maxn];
bool haveans=false;

int min(int x,int y )
{
return x<y?x:y;
}

//#define Open_File
int main()
{
#ifdef Open_File
freopen("vijos1965.in","r",stdin);
//freopen("vijos1965.out","w",stdout);
#endif
scanf("%d%d",&n,&c);
for (int i=1;i<n;i++) scanf("%d",&ans[i]);
int top=min(n-1,2*c),bottom=1; //优化一
bool go=n<=c+1;

for (x=0;x<c;x++) for (a=0;a<c;a++) for (b=0;b<c;b++)
if (go||((long long int) ans[c]*a+b)%c==ans[c+1]) //优化二
{
f=x;
bool z=true;
for (int i=bottom;i<=top;i++)
{
if (i>c&&f!=ans[i]||f%i!=ans[i]) //优化三
{
z=false;
break;
}
f=((long long int)a*f+b)%c;
}
if (z)
{
printf("%d %d %d\n",x,a,b);
haveans=true;
}
}
if (!haveans) printf("Unsuccessful Hack Attempt\n");
return 0;
}

doc的题解对我很有启发，我另外加了一个优化，见
http://blog.csdn.net/whoispo/article/details/49009149

本题第五个点，满足n<c，且c=400，n=390。虽然本题有O(c^2n)的算法，但是常数比较大。

然而实际上，暴力就已经足以通过所有数据点，但要求程序有细腻的常数优化。我这里给出自己的代码。

需要注意的是：（1）第n-1个值会立刻筛掉大量不可能解（2）很多运算可以预处理得到，包括取余数和数列通项中的系数

memset( ans , false , sizeof(ans) ) ;
int flag=0;
// savemod[i][j][k] = (i*j+k)%m
// ii[k] = i^{k-1}
// jj[k] = 1+i+i^2+...+i^{k-2}
for (i=0;i<m;++i)
for (j=0;j<m;++j) {
int tmp = (i*j)%m ;
for (k=0;k<m-tmp;++k) savemod[i][j][k] = tmp+k;
for (k=0;k<tmp;++k) savemod[i][j][k+m-tmp] = k;
}
for (ii[1]=1,jj[1]=0,i=0;i<m;++i) {
for (k=2;k<n;++k)
ii[k] = savemod[ii[k-1]][i][0],
jj[k] = savemod[jj[k-1]][i][1];
for (j=0;j<m;++j)
for (k=0;k<m;k++)
if ( savemod[ii[n-1]][k][savemod[j][jj[n-1]][0]]%(n-1) == a[n-1] &&
savemod[ii[2]][k][savemod[j][jj[2]][0]]%2 == a[2] ) {
for(l=n-2;l>=3 &&
savemod[ii[l]][k][savemod[j][jj[l]][0]]%l==a[l];
--l) ;
if (l==2) {
ans[k][i][j] = true;
flag = 1;
}
}
}
if (flag==0) puts("Unsuccessful Hack Attempt");
else {
for (i=0;i<m;++i)
for (j=0;j<m;++j)
for (k=0;k<m;++k)
if (ans[i][j][k])
printf("%d %d %d\n",i,j,k);
}

在运气比较好的情况下，即便是VijosEx评测器，也可以做到625ms通过那个极限点。

测试数据 #0: Accepted, time = 0 ms, mem = 336168 KiB, score = 5
测试数据 #1: Accepted, time = 0 ms, mem = 336168 KiB, score = 5
测试数据 #2: Accepted, time = 0 ms, mem = 336176 KiB, score = 5
测试数据 #3: Accepted, time = 0 ms, mem = 336176 KiB, score = 5
测试数据 #4: Accepted, time = 625 ms, mem = 336168 KiB, score = 5
测试数据 #5: Accepted, time = 0 ms, mem = 336176 KiB, score = 5
测试数据 #6: Accepted, time = 31 ms, mem = 336172 KiB, score = 5
测试数据 #7: Accepted, time = 0 ms, mem = 336176 KiB, score = 5
测试数据 #8: Accepted, time = 31 ms, mem = 336176 KiB, score = 5
测试数据 #9: Accepted, time = 0 ms, mem = 336168 KiB, score = 5
测试数据 #10: Accepted, time = 0 ms, mem = 336168 KiB, score = 5
测试数据 #11: Accepted, time = 15 ms, mem = 336176 KiB, score = 5
测试数据 #12: Accepted, time = 0 ms, mem = 336172 KiB, score = 5
测试数据 #13: Accepted, time = 0 ms, mem = 336168 KiB, score = 5
测试数据 #14: Accepted, time = 15 ms, mem = 336176 KiB, score = 5
测试数据 #15: Accepted, time = 78 ms, mem = 336176 KiB, score = 5
测试数据 #16: Accepted, time = 46 ms, mem = 336176 KiB, score = 5
测试数据 #17: Accepted, time = 31 ms, mem = 336176 KiB, score = 5
测试数据 #18: Accepted, time = 62 ms, mem = 336168 KiB, score = 5
测试数据 #19: Accepted, time = 31 ms, mem = 336176 KiB, score = 5