Codeforces 852F Product transformation

根据题意首先整理一下规律:

假如原始数组为 2 2 2 2,那么变换几次之后的数组分别为:

 

2 2 2 2
4 4 4 2
16 16 8 2
256 128 16 2

我们只关心指数,每个数的指数为:

1 1 1 1
2 2 2 1
4 4 3 1
8 7 4 1

这样原来每两个数相乘,就变成了每两个数相加。为了让规律再明显一点,我们计算前后两个数的差:

0 0 0
0 0 1
0 1 1
1 2 1

可以发现这是杨辉三角。杨辉三角第m行的第i个数字就是\(C_m^i\)因此数组从右往左第k个数的指数就是\(Sigma_{i=1}^k C_m^i\),其中m是变换的次数。下面的任务就是如何计算出每一个\(C_m^i\)。

计算mCi时,分子或分母相乘时很容易造成溢出。不过,由于题目只要求计算对某个Q取模的结果,我们可以充分利用这一点。不过需要注意的是,mCi这里并不是对Q取模,而应该对\(\phi\)取模。考虑到\(a^0 === 1\),即\(a^0 mod Q == 1\),\(\phi\)是下一次对Q取模等于一的幂——即余数每\(\phi\)次循环一遍。要计算\(\phi\),只需要不断计算a的幂取模的结果即可,这些结果后面还用得上;如果发现取模为1了,就可以停止计算。

回到计算mCi的问题上,分子的计算可以利用\(ab mod c = (a mod c)(b mod c) mod c\)计算,比较难办的是分母如何计算。分母的计算可以利用费马小定理,得到\(a^{-1} = a^{p-2} mod p\),将\(a^{-1}\)的计算改为计算\(a^{p-2} mod p\)。利用快速幂取模即可。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _852F
{
    class Program
    {
        static long exp_mod(long a, long b, int mod)
        {
            if (b == 0)
                return 1;
            if (b == 1)
                return a % mod;
            long t = exp_mod(a, b / 2, mod);
            t = (t * t) % mod;

            if (b % 2 == 1)
                t = (t * a) % mod;
            return t;
        }

        static long[] C(int n, int q)
        {
            int k = n / 2;
            if (n % 2 == 0)
            {
                k--;
            }
            List<long> arr = new List<long>();
            arr.Add(1);
            long a = 1;
            int n2 = n;
            for (int i = 1; i <= k; i++)
            {
                a = (a * n2) % q;
                a = (a * exp_mod(i, q-2, q)) % q;
                n2--;
                arr.Add(a);
            }

            List<long> arr2 = ((IEnumerable<long>)arr).Reverse().ToList();

            if (n % 2 == 0)
            {
                a = (a * n2) % q;
                a = (a * exp_mod(k + 1, q - 2, q)) % q;
                arr.Add(a);
            }

            arr.AddRange(arr2);

            return arr.ToArray();
        }

        static void Main(string[] args)
        {
            int[] t = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            int n = t[0];
            int m = t[1];
            int a = t[2];
            int q = t[3];

            List<long> pow = new List<long>();
            pow.Add(1);
            long p = 1;
            while (true)
            {
                p = (p * (a % q)) % q;
                if (p != 1)
                {
                    pow.Add(p);
                }
                else
                {
                    break;
                }
            }

            long[] c = C(m, pow.Count);

            List<long> arr = new List<long>();
            arr.Add(a % q);
            int tmp = 1;
            for (int i = 1; i < n; i++)
            {
                if (i <= m)
                {
                    tmp += (int)c[i];
                    tmp %= pow.Count;
                }
                arr.Add(pow[tmp]);
            }

            arr.Reverse();

            Console.WriteLine(string.Join(" ", arr));
        }
    }
}

Default Comments (0)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Disqus Comments (0)

dontpanic92-cn