题解 P6608 【[Code+#7]神秘序列】

WYXkk · 2020-11-11 13:41:55 · 题解

在 MO 课上听到了和这题类似的题，所以跑来写篇题解（

首先发现一个性质：我们必须保证任何时刻 a_i\le i。

否则，一旦 a_i>i，那么我们再也无法对 a_i 操作，它就不可能降为 0。

因此，每次一定是选择 a_i=i 的最小 i 操作。

因此我们可以把整个过程反过来，相当于每次选择最小的 i 使 a_i=0，然后 a_1,a_2,\cdots,a_{i-1} 全部减一，a_i 变成 i。

然后通过模拟这个过程可以拿到 35pts 的好成绩。

接下来我们可以考虑找规律，因此打个表。

打表程序 ↓

const int N=3000005;
int a[N];
int main()
{
    freopen("out.txt","w",stdout);int n=0;
    F(i,1,999)
    {
        printf("%3d:",i);
        int u=1;while(a[u]){--a[u];++u;}a[u]+=u;
        if(u>n) n=u;
        F(j,1,n) printf("%d ",a[j]);puts("");
    }
    return 0;
}

然后打出来的表大概长这样 ↓（截取了一部分）

  1:1 
  2:0 2 
  3:1 2 
  4:0 1 3 
  5:1 1 3 
  6:0 0 2 4 
  7:1 0 2 4 
  8:0 2 2 4 
  9:1 2 2 4 
 10:0 1 1 3 5 
 11:1 1 1 3 5 
 12:0 0 0 2 4 6 
 13:1 0 0 2 4 6 
 14:0 2 0 2 4 6 
 15:1 2 0 2 4 6 
 16:0 1 3 2 4 6 
 17:1 1 3 2 4 6 
 18:0 0 2 1 3 5 7 
 19:1 0 2 1 3 5 7 
 20:0 2 2 1 3 5 7 
 21:1 2 2 1 3 5 7 
 22:0 1 1 0 2 4 6 8 
 23:1 1 1 0 2 4 6 8 
 24:0 0 0 4 2 4 6 8 
 25:1 0 0 4 2 4 6 8 

每一位似乎都有循环节，但是这个循环节随着数增大越来越长，非常难受，很难处理。

事实上是，我们找规律的对象选错了。

我们可以对每次操作的 a 找规律，得到下面这张表 ↓（截取了一部分）

每两个出现一个 1，每六个出现一个 2。还有其它规律吗？

我们去掉所有 1：2,3,4,2,5,6,2,3,7,2,8,4,2,3,9,2,10,5,2,3,11,2,4,12,2,3,6,2,13,14,2,3,4

现在是每三个一个 2，我们再去掉所有 2：3,4,5,6,3,7,8,4,3,9,10,5,3,11,4,12,3,6,13,14,3,4,5,7,3,15,16,4,3,8,6,5,3,1

剩下的是每四个一个 3，我们再去掉所有 3：4,5,6,7,8,4,9,10,5,11,4,12,6,13,14,4,5,7,15,16,4,8,6,5,17,4,18,9,19,7

剩下的是每五个一个 4，后面以此类推。

因此，我们得到规律：\ge m 的操作中，第一个操作 m，后面每 m+1 次操作一次 m。

仔细想想会发现这个规律是显然成立的。也就是说规律发现比规律证明难？

因此我们只需要想办法定下 n 的值，然后就能 O(n) 定出每个数被操作多少次，然后就可以用前缀和搞一下得出所有数最终值。

至于 n 值怎么定？先本地二分打表，求出一些 n 对应的最小 s；然后查表，求出 s 对应的 n 在哪个范围内；然后在这个范围内二分求出 s 对应的 n。

然后这题就做完了。

参考代码：

打表 ↓

const int N=3000005;
int a[N];
int check(ll s)
{
    int i=1;while(s){s=s*i/(i+1);++i;}
    return i;//这里似乎写错了，但也过了？/yun
}
ll doit(int n)
{
    ll l=1,r=2000000000000ll;
    while(l!=r)
    {
        ll mid=(l+r)>>1;
        if(check(mid+n)>=n) r=mid;else l=mid+1;
    }
    return l;
}       
int main()
{
    freopen("out.txt","w",stdout);
    F(i,1,200) printf("%lldll,",doit(i*10000));
    return 0;
}

最终程序 ↓

const int N=3000005;
ll tmp[]={/*表省略*/};
ll a[N],b[N];
int check(ll s)
{
    int i=1;while(s){s=s*i/(i+1);++i;}
    return i-1;
}
int doit(ll a,int l,int r)
{
    while(l!=r)
    {
        int mid=(l+r)>>1;
        if(check(a+mid)<=mid) r=mid;else l=mid+1;
    }
    return l;
}
int main()
{
    ll s=rd();
    int i=1;while(s>=tmp[i]) ++i;
    int n=doit(s,(i-1)*10000,i*10000);
    printf("%d\n",n);s+=n;
    F(i,1,n) {ll u=s*i/(i+1);a[i]=s-u;s=u;}
    F(i,1,n) b[i]=a[i]*i;
    UF(i,n,2) {b[i-1]-=a[i];a[i-1]+=a[i];}
    F(i,1,n) printf("%lld ",b[i]);
    return 0;
}