AT_abc137_f

VERACITY · 2023-07-19 10:47:37 · 题解

在下无才，只得讲得俗一些

题意

给出长为 p 的 01 子串，使得 f(x)= \displaystyle\sum_{i=0}^{p-1} b_ix^i，且 f(x) \equiv a_x\pmod p，0 \leq b_x \leq p-1。

前置

先说 CRT 的剥离思想。简单来讲就是通过构造多个式子，将原来的多个要求剥离开来，消除原要求的影响使最后求得的答案满足所有的原要求。推广至本题，我们可以对每一个式子分别构造一个量，使此式子只对对应要求产生影响，最后答案即可通过求和得出。

思路

由剥离思想得，在 a_x = 1 时构造一个函数 g(i) 使 i = x 时 g(i) = 1，i \not = x 时 g(i)=0。这样使求和后只对 f(x) 产生影响。
由于题目要求是在模意义下，且值为 1，啊非常快的就能想到用费马小定理构造出 g(i) = 1 - (i-x)^{p-1}，后面的 (i-x)^{p-1} 用二项式定理展开得 \displaystyle\sum_{j=0}^{p-1} \binom{p-1}{j}i^{p-j-1}(-x)^i。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mx=1e4;
ll p,cnt,a[mx],fac[mx],inv[mx],ans[mx];
ll ksm(int x)
{
    ll res=x,ans=1,k=p-2;
    while(k)
    {
        if(k&1)ans=ans*res%p;
        res=res*res%p,k>>=1;
    }
    return ans;
}
ll C(ll n,ll m){return fac[n]*inv[m]%p*inv[n-m]%p;}
//乘法逆元求组合数 
int main()
{
    cin >> p;
    for(int i=0;i<p;i++){cin >> a[i];cnt+=a[i];}
    fac[0]=inv[0]=1;
    for(int i=1;i<p;i++) fac[i]=fac[i-1]*i%p;
    inv[p-1]=ksm(fac[p-1]);
    for(int i=p-1;i>1;i--) inv[i-1]=inv[i]*i%p;

    for(int i=0;i<p;i++)
        if(a[i])
        {
            int res=1;
            for(int j=0;j<p;j++)
                ans[p-j-1]=(ans[p-j-1]+res)%p,res=res*(p-i)%p;
        }
    for(int i=0;i<p;i++)
    {
        ans[i]=ans[i]*C(p-1,i)%p;
        if(!i) ans[i]=(ans[i]-cnt+p)%p;
        if(ans[i]) ans[i]=p-ans[i];
        cout<<ans[i]<<" ";
    }
    //此处求法具体可参考原来各位大佬的题解
    return 0;
}