暴力法无法解出，可能要使用dp和数学知识

Question

急需AC难题：G. Math, math everywhere
原题链接：https://codeforces.com/problemset/problem/765/G
洛谷链接：https://www.luogu.com.cn/problem/CF765G

建议直接点击上方链接进去答题，必须能全部AC通过才算解题成功

Math, math everywhere

题面翻译

给定 $N$ 的因式分解形式 $\prod_{i=1}^np_i^{\alpha_i}$ 和一个长为 $m$ 的字符串 $s$。

求 $k$ 的个数，使得 $0\leq k<N$ 且

$$\gcd(k+i,N)=1 \text{ if and only if }s_i=1$$

模 $10^9+7$。

$m \leq 40$，$n\leq 5\times 10^5$，$p_i, \alpha_i \leq 10^9$。

题目描述

If you have gone that far, you'll probably skip unnecessary legends anyway...

You are given a binary string

and an integer

. Find the number of integers $ k $ , $ 0<=k<N $ , such that for all $ i=0 $ , $ 1 $ , ..., $ m-1 $

Print the answer modulo $ 10^{9}+7 $ .

输入格式

In the first line of input there is a string $ s $ consisting of $ 0 $ 's and $ 1 $ 's ( $ 1<=|s|<=40 $ ).

In the next line of input there is an integer $ n $ ( $ 1<=n<=5·10^{5} $ ).

Each of the next $ n $ lines contains two space-separated integers $ p_{i} $ , $ α_{i} $ ( $ 1<=p_{i},α_{i}<=10^{9} $ , $ p_{i} $ is prime). All $ p_{i} $ are distinct.

输出格式

A single integer — the answer to the problem.

样例 #1

样例输入 #1

1
2
2 1
3 1

样例输出 #1

2

样例 #2

样例输入 #2

01
2
3 2
5 1

样例输出 #2

15

样例 #3

样例输入 #3

1011
1
3 1000000000

样例输出 #3

411979884

Answer 1

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define low(x) ((x)&-(x))
#define add(a,b) a=((a)+(b))%1000000007
#define mod 1000000007
#define ll long long
using namespace std;

int g[79691777],G[6029313],h[41],num[1048576],m,n,M,MM,M2,MM2,id,id2,i,j,k,l,J,K,sum;
ll p[500001],P[41],A,L,L2,L3,LL2,ans,Ans,s1,s2,S1,S2,S;
char st[41];
pair<ll,int> s;
map<ll,int> f[13];
map<ll,int> :: iterator I;

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}
int turn(int i,int j,int k,int M,int L2) {return (i*(L2+1)+j)*(M+1)+k;}
ll get(ll t,int x,int y)
{
    int i,ans=0;
    t>>=x;y-=x-1;
    while (y)
    {
        if (y>20) ans+=num[t&(P[20]-1)],y-=20,t>>=20;
        else {ans+=num[t&(P[y]-1)];break;}
    }
    return ans;
}

int main()
{
    #ifdef file
    freopen("CF765G.in","r",stdin);
    #endif

    P[0]=1;
    fo(i,1,40) P[i]=P[i-1]*2;
    scanf("%s",st+1);m=strlen(st+1);Ans=1;
    scanf("%d",&n);
    fo(i,1,n) scanf("%lld%lld",&p[i],&A),Ans=(Ans*qpower(p[i],A-1))%mod;
    fd(i,m,1) s1=s1*2+(st[i]-'0'),sum+=!(st[i]-'0');

    l=(1ll<<20)-1;
    fo(i,1,l) num[i]=num[i-low(i)]+1;
    sort(p+1,p+n+1);
    L=(1ll<<m)-1;s1^=L;

    if (p[1]<=23)
    f[0][0]=1;
    else
    if (p[1]<m)
    M=m-p[1],L2=P[M]-1,g[get(s1,M,p[1]-1)]=1;
    else
    h[sum]=1;
    l=1;

    while (l<=n && p[l]<=23)
    {
        for (I=f[l-1].begin(); I!=f[l-1].end(); ++I)
        {
            s=*I;
            for (i=S=0; i<m; i+=p[l]) S|=1ll<<i;
            fo(j,0,p[l]-1)
            {
                s2=s.first|S;
                if ((s2&s1)==s2)
                {
                    if (l==n || p[l+1]>23)
                    {
                        if (l==n || p[l+1]>=m)
                        k=get(s2^s1,0,m-1),add(h[k],s.second);
                        else
                        {M=m-p[l+1];L2=P[M]-1;M2=p[l+1]-M;k=get(s2^s1,M,p[l+1]-1);add(g[turn(s2&(P[M]-1),s2>>p[l+1],k,M2,L2)],s.second);}
                    }
                    else
                    add(f[l][s2],s.second);
                }
                S=(S*2)&L;
            }
        }
        ++l;
    }
    if (!M && l<=n && p[l]<m) {printf("0\n");return 0;}
    while (l<=n && p[l]<m)
    {
        S=get(s1,M,p[l]-1);S1=s1&(P[M]-1),S2=s1>>p[l];
        fd(i,L2,0)
        {
            fd(j,L2,0)
            {
                fo(k,0,M2)
                {
                    id=turn(i,j,k,M2,L2);
                    if (g[id])
                    {
                        s2=g[id];g[id]=0;
                        if (l==n || p[l+1]>=m)
                        {
                            fo(J,0,M-1)
                            if ((s1&P[J]) && (s1&P[J+p[l]]))
                            K=num[(i|P[J])^S1]+num[(j|P[J])^S2]+k,add(h[K],s2);
                            if (k)
                            K=num[i^S1]+num[j^S2]+k-1,add(h[K],1ll*s2*k%mod);
                            K=num[i^S1]+num[j^S2]+k,add(h[K],1ll*s2*(S-k)%mod);
                        }
                        else
                        {
                            fo(J,0,M-1)
                            if ((s1&P[J]) && (s1&P[J+p[l]]))
                            add(g[turn(i|P[J],j|P[J],k,M2,L2)],s2);
                            if (k)
                            add(g[turn(i,j,k-1,M2,L2)],1ll*s2*k%mod);
                            add(g[turn(i,j,k,M2,L2)],1ll*s2*(S-k)%mod);
                        }
                    }
                }
            }
        }

        ++l;
        if (l<=n && p[l]<m)
        {
            MM=m-p[l],LL2=P[MM]-1,MM2=p[l]-MM;
            S1=get(s1,MM,M-1);S2=get(s1,p[l-1],p[l]-1);
            fo(i,0,L2)
            {
                fo(j,0,L2)
                {
                    fo(k,0,M2)
                    {
                        id=turn(i,j,k,M2,L2);
                        if (g[id])
                        {
                            id2=turn(i&(P[MM]-1),j>>(p[l]-p[l-1]),k+(S1-(num[i]-num[i&(P[MM]-1)]))+(S2-(num[j]-num[j>>(p[l]-p[l-1])])),MM2,LL2);
                            add(G[id2],g[id]);
                        }
                    }
                }
            }
            memcpy(g,G,((LL2+1)*(LL2+1)*(MM2+1))*4);
            M=MM,L2=LL2,M2=MM2;
            memset(G,0,((L2+1)*(L2+1)*(M2+1))*4);
        }
    }
    while (l<=n)
    {
        fo(i,0,m)
        {
            if (i)
            add(h[i-1],1ll*h[i]*i%mod);
            h[i]=1ll*h[i]*(p[l]-m+(sum-i))%mod;
        }
        ++l;
    }

    ans=h[0];
    printf("%lld\n",ans*Ans%mod);

    fclose(stdin);
    fclose(stdout);
    return 0;
}