• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

[ZJOI2009] 硬币游戏

开发技术 开发技术 2周前 (05-01) 5次浏览

一、题目

点此看题

二、解法

看到这种多次操作的题一定要往倍增方面想。

矩阵加速显然是可以的,就是有点慢,但是在部分情况下多项式能代替矩阵加速的功能,不难构造下列的多项式,我们只需要求初始数组和它在模 (x^{2n}) 意义下的循环卷积即可:

[(x+x^{2n-1})^T
]

暴力跑是 (O(nlog nlog T)) 的,我们可以把正面朝上记为 (0),反面朝上记为 (1),不难发现整个过程都是模 (2) 意义下的,记得有人说过:模小质数的多项式可以考虑有没有什么可以快速计算的形式

现在就乱搞一下嘛,可以想想二项式展开:

[(x+x^{2n-1})^t=sum_{i=0}^{t}{tchoose i}cdot x^{i}cdot x^{(t-i)(2n-1)}
]

小质数遇见了组合数,看能不能用 (tt lucas) 搞一下,不难发现当 (t)(2^k) 时只有 (i=0)(i=t) 贡献为 (1),其他情况都被模成 (0) 了,考虑实际意义就是只有两边延伸到的最远地方才有贡献。可以把 (T) 做二进制分解,因为操作是可以拆开进行的,然后直接对原数组改一改就行了,时间复杂度 (O(nlog n))

(t=0) 的时候单独讨论一下,因为要按照他的方式输出答案嘛。

#include <cstdio>
const int M = 200005;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,c[2][M];
signed main()
{
    n=read()*2;m=read();
    for(int i=0;i<n/2;i++)
        c[k][2*i]=read()-1;
    for(int a=2;a<=m;a<<=1)
    {
        if(m&a)
        {
            for(int i=0;i<n;i++)
                c[k^1][i]=c[k][(i+a)%n]^c[k][((i-a)%n+n)%n];
            k^=1;
        }
    }
    if(m&1)
    {
        for(int i=0;i<n/2;i++)
            printf("0 %d ",(c[k][i*2]^c[k][((i+1)*2%n+n)%n])+1);
    }
    else
    {
        for(int i=0;i<n/2;i++)
            printf("%d 0 ",c[k][2*i]+1);
    }
}

程序员灯塔
转载请注明原文链接:[ZJOI2009] 硬币游戏
喜欢 (0)