Loading...

「hihoCoder 1230」The Celebration of Rabbits

check评论:0 条 remove_red_eye浏览量:237 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-12-20

枚举$x$,构造$a_i$的生成函数$A=\sum\limits_{a_i \in [x,m+x]} x^{a_i}$,$FWT$后对每一项快速幂,再$IFWT$即可,$A[0]$就是每一次的答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7,g=5e8+4;
int C[3010],n,m,l,r,lim=2048;
void FWT(int *x,int flag)
{
    for(int mid=1;mid<lim;mid<<=1)
    {
        for(int k=0,r=(mid<<1);k<lim;k+=r)
        {
            for(int i=0;i<mid;i++)
            {
                int dx=x[i+k],dy=x[i+mid+k];
                x[i+k]=(dx+dy)%mod,x[i+k+mid]=(dx-dy+mod)%mod;
                if(flag==0)
                {
                    x[i+k]*=g;
                    x[i+k]%=mod;
                    x[i+mid+k]*=g;
                    x[i+mid+k]%=mod;
                }
            }
        }
    }
}
int ksm(int a,int qaq)
{
    int res=1;
    while(qaq)
    {
        if(qaq&1)
        {
            res=res*a%mod;
        }
        a=a*a%mod;
        qaq>>=1;
    }
    return res;
}
signed main()
{
    while(cin>>n>>m>>l>>r)
    {
        int ans=0;
        for(int i=l;i<=r;i++)
        {
            memset(C,0,sizeof(C));
            for(int j=0;j<=m;j++)
            {
                C[j+i]++;
            }
            FWT(C,1);
            for(int j=0;j<lim;j++)
            {
                C[j]=ksm(C[j],2*n+1);
            }
            FWT(C,0);
            ans+=C[0];
            ans%=mod;
        }
        cout<<ans<<"\n";
    }
}

chevron_left min-max容斥初学
HDU5909 Tree Cutting chevron_right

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名