首页 > 编程学习 > 9.2

9.2

发布时间:2022/9/3 1:54:49

ABC137F

题意:

给定一个素数\(p\)\(a_0\sim a_{p-1}\in\{0,1\}\)

找到至多\(p-1\)次的多项式\(f(x)=\sum_{i=0}^{p-1}b_ix^i(b_i\in[0,p-1])\)

满足\(f(i)\equiv a_i\ (mod\ p)\)

\(2\leq p<3000\)

题解:

神仙构造题,这个其实很像中国剩余定理,而且\(p\)是素数满足费马小定理,\(a_i\)满足只有\(0\)\(1\),考虑构造:

如果\(a_i=1\),那么\(f(x)+=(g(x)=1-(x-i)^{p-1})\)

这个\(g(x)\)当且仅当\(x=i\)时,\(g(x)=1\),其他情况下因为费马小定理,后面那一项等于\(1\),总体等于零,不会对其他项造成影响。

这个式子用二项式定理直接展开。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
    const int N=1e6+10,mod=998244353,inf=2e15;
    void __init(int n=2000) {}
    inline void main()
    {
        auto fast=[&](int x,int k,int mod) -> int
        {
            int ret=1;
            while(k)
            {
                if(k&1) ret=ret*x%mod;
                x=x*x%mod;
                k>>=1;
            }
            return ret;
        };
        int n;
        cin>>n;
        vector<int> a(n);
        for(int i=0;i<n;++i)
        {
            int x;
            cin>>x;
            if(!x) continue;
            //1-(x-i)^{n-1}
            ++a[0];
            int pw=1,com=1;
            for(int j=n-1;~j;--j)
            {
                a[j]-=pw*com%n;
                a[j]%=n;
                pw=pw*(-i)%n;
                com=com*j%n*fast(n-j,n-2,n)%n;
                
            }
        }
        for(int i=0;i<n;++i)
        {
            cout<<(a[i]+n)%n<<' ';
        }
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    red::__init();
    int qwq=1; //cin>>qwq;
    while(qwq--) red::main();
    return 0;
}
/*
1 7 5 6 8 2 6 5

0 8 5 6 8 0 8 5
3
5 6 5
3 8 5
2
3
8
*/

ABC138F

题意:

给定\(L,R\),求有多少对数字\(L\leq x\leq y\leq R\),满足\(x\mod y=x\oplus y\)

\(0\leq L\leq R\leq 10^{18}\)

\(1e9+7\)

题解:

转化一下取模

如果\(2x\leq y\),那么\(y-x>y\%x\)

如果\(2x>y\),那么\(y-x=y\%x\)

\(x\oplus y\geq y-x\)

所以如果\(2x\leq y\),不可能满足要求。

\(2x>y\)时,

\(x\)\(y\)二进制下的最高位相同,如果要满足\(y-x=y\oplus x\),那么\(y\&x=x\)

总结一下就是\(x,y\)的二进制位数相同,而且\(y\&x=x\)

考虑数位\(dp\),但是很难容斥,用另一种状态设置,\(dp[pos][x1][x2]\)表示第\(pos\)位,是否到达下界,是否到达上界。

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
    const int N=1e6+10,mod=1e9+7,inf=2e15;
    void __init(int n=2000) {}
    inline void main()
    {
        int l,r;
        cin>>l>>r;
        vector<int> d,u;
        vector dp(100,vector(2,vector<int>(2,-1)));
        function<int(int,int,int)> dfs=[&](int pos,int x1,int x2) -> int 
        {
            if(pos<0) return 1;
            if(~dp[pos][x1][x2]) return dp[pos][x1][x2];
            int &ret=dp[pos][x1][x2];ret=0;
            int t1=x1?d[pos]:0,t2=x2?u[pos]:1;
            for(int y=t1;y<=t2;++y)
                for(int x=t1;x<=y;++x)
                    ret=(ret+dfs(pos-1,x1&(x==t1),x2&(y==t2)))%mod;
            return ret;
        };
        auto solve=[&](int l,int r) -> int
        {
            while(l) d.emplace_back(l&1),l>>=1;
            while(r) u.emplace_back(r&1),r>>=1;
            // reverse(d.begin(),d.end());
            // reverse(u.begin(),u.end());
            int ans=0,tl=d.size(),tr=u.size();
            for(int i=tl;i<=tr;++i) ans=(ans+dfs(i-2,i==tl,i==tr))%mod;
            return ans;
        };
        cout<<solve(l,r)<<'\n';
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    red::__init();
    int qwq=1; //cin>>qwq;
    while(qwq--) red::main();
    return 0;
}
/*
1 7 5 6 8 2 6 5

0 8 5 6 8 0 8 5
3
5 6 5
3 8 5
2
3
8
*/

CF1717E

题意:

\[\sum_{a+b+c=n}lcm(c,gcd(a,b)) \]

\(n\leq 10^5\)

题解:

枚举\(gcd(a,b)=d\)

然后枚举\(a+b=t*d\)\(t\),这里是调和级数。

那么\(c=n-t*d\)

然后就想知道有多少对\((a,b)\),满足\(a+b=t\)\(gcd(a,b)=1\)

如果\(a\)\(b\)互质,那么\(a\)\(a+b\)互质。

\(a+b=t\),所以\(a\)\(t\)互质。

所以这个数量等于\(\varphi(t)\)

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
#define double long double
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define lowbit(i) ((i)&(-i))
#define mid ((l+r)>>1)
#define eps (1e-15)
    const int N=1e6+10,mod=1e9+7,inf=2e15;
    void __init(int n=2000) {}
    inline void main()
    {
        auto lcm=[&](int x,int y) -> int
        {
            return x*y/__gcd(x,y);
        };

        int n;
        cin>>n;

        vector<int> phi(n+1);
        iota(phi.begin(),phi.end(),0);
        for(int i=1;i<=n;++i)
        {
            for(int j=2*i;j<=n;j+=i) phi[j]-=phi[i];
        }
        int ans=0;
        for(int d=1;d<=n-2;++d)
        {
            for(int g=2*d;g<=n;g+=d)
            {
                int c=n-g;
                ans=(ans+lcm(c,d)*phi[g/d])%mod;
            }
        }
        cout<<ans<<'\n';
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    red::__init();
    int qwq=1; //cin>>qwq;
    while(qwq--) red::main();
    return 0;
}
/*
1 7 5 6 8 2 6 5

0 8 5 6 8 0 8 5
3
5 6 5
3 8 5
2
3
8
*/
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号