头像

Foraino0267

$\href{https://www.luogu.com.cn/user/139577#main}{乌拉拉得第一♪}$




离线:11天前


最近来访(318)
用户头像
acwing_xyy
用户头像
GymDarius
用户头像
垫底抽風
用户头像
yxc的小迷妹1
用户头像
Eager
用户头像
Bochi
用户头像
hansang
用户头像
种花家的虎式坦克
用户头像
海问香
用户头像
xiuzhiyuan
用户头像
陌丨落
用户头像
163.com
用户头像
基思卡人---奇衡三
用户头像
StkOvflow
用户头像
Fireflylight
用户头像
C++萌新马
用户头像
SKG_G
用户头像
_Kouki_
用户头像
阿萨德风格
用户头像
迎风飘扬

新鲜事 原文

怎么这么晚还在卷



不想存本地,丢这里好了

#include<bits/stdc++.h>
typedef long long ll;
#define add(a,b) ((a+b<mod)?(a+b):(a+b-mod))
#define minus(a,b) ((a>=b)?(a-b):(a-b+mod))
#define Poly vector<ll>
using namespace std;

const int N=4e6+50;
const int g=3,mod=998244353,gi=332748118;

int qpow_num(int a,int b) {
    int ans=1;
    while(b) {
        if(b&1) ans=1ll*ans*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return ans;
}
int pow_inv(int x) {
    return qpow_num(x,mod-2);
}

int powg[N],powgi[N],powinv[N];
void init() {
    powinv[1]=1;
    for(int i=2;i<=N-50;++i) powinv[i]=1ll*(mod-mod/i)*powinv[mod%i]%mod;
    for(int i=1,j=0;i<=mod+1;i<<=1,++j) powg[j]=qpow_num(g,(mod-1)/i),powgi[j]=qpow_num(gi,(mod-1)/i); 
}

Poly operator +(Poly a,Poly b) {
    Poly ans;
    ans.clear();
    for(int i=0;i<min(a.size(),b.size());++i) ans.push_back(add(a[i],b[i]));
    if(a.size()<b.size()) for(int i=a.size();i<b.size();++i) ans.push_back(b[i]);
    else for(int i=b.size();i<a.size();++i) ans.push_back(a[i]);
    return ans;
}

Poly operator -(Poly a,Poly b) {
    Poly ans;
    ans.clear();
    for(int i=0;i<min(a.size(),b.size());++i) ans.push_back(minus(a[i],b[i]));
    if(a.size()<b.size()) for(int i=a.size();i<b.size();++i) ans.push_back(minus(0,b[i]));
    else for(int i=b.size();i<a.size();++i) ans.push_back(a[i]);
    return ans;
}

Poly operator *(Poly a,int b) {
    Poly ans;
    ans.clear();
    for(int i=0;i<a.size();++i) ans.push_back(a[i]*b%mod);
    return ans;
}
Poly operator *(int a,Poly b) {
    return b*a;
}
Poly operator /(Poly a,int b) {
    Poly ans;
    ans.clear();
    for(int i=0;i<a.size();++i) ans.push_back(a[i]*pow_inv(b)%mod);
    return ans;
}

int rev[N];
int w[N];
void ntt(Poly &a,int type) {
    w[0]=1;
    for(int i=0;i<a.size();++i) if(i<rev[i]) swap(a[i],a[rev[i]]);
    for(int mid=1,tims=1;mid<a.size();mid<<=1,++tims) {
        int g1=(type==1)?powg[tims]:powgi[tims];
        for(int i=1;i<mid;++i) w[i]=1ll*w[i-1]*g1%mod;
        for(int i=0;i<a.size();i+=mid<<1)
            for(int j=0;j<mid;++j) {
                int y=1ll*a[i+j+mid]*w[j]%mod;
                a[i+j+mid]=minus(a[i+j],y),a[i+j]=add(a[i+j],y);
            }
    }
}

Poly operator *(Poly a,Poly b) {
    Poly ans;
    ans.clear();
    int siza=a.size(),sizb=b.size(),siz=a.size()+b.size()-1,bit=0,tot=1;
    while(tot<siz) tot<<=1,++bit;
    for(int i=0;i<tot;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
    a.resize(tot,0),b.resize(tot,0);
    ntt(a,1),ntt(b,1);
    for(int i=0;i<tot;++i) ans.push_back(a[i]*b[i]%mod);
    ntt(ans,-1);
    int intot=pow_inv(tot);
    for(int i=0;i<tot;++i) ans[i]=ans[i]*intot%mod;
    Poly lstans(ans.begin(),ans.begin()+siz);
    return lstans;
}

Poly inv(Poly a,int realsiz=0) {
    Poly ans;
    ans.clear();
    int siz=(realsiz)?realsiz:a.size();
    int bit=0,tot=1;
    while(tot<siz) tot<<=1,++bit;
    a.resize(tot,0);
    ans.push_back(pow_inv(a[0]));
    for(int len=1;len<a.size();len<<=1) {
        Poly tmp(a.begin(),a.begin()+(len<<1));
        Poly anss;
        anss.clear();
        int sizz=tmp.size()+ans.size()*2-1,bitt=0,tott=1;
        while(tott<sizz) tott<<=1,++bitt;
        for(int i=0;i<tott;++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bitt-1));
        tmp.resize(tott,0),ans.resize(tott,0);
        ntt(tmp,1),ntt(ans,1);
        for(int i=0;i<tott;++i) anss.push_back(minus(2ll*ans[i]%mod,1ll*tmp[i]*ans[i]%mod*ans[i]%mod));
        ntt(anss,-1);
        int intot=pow_inv(tott);
        for(int i=0;i<tott;++i) anss[i]=anss[i]*intot%mod;
        ans.clear();
        for(int i=0;i<(len<<1);++i) ans.push_back(anss[i]);
    }
    Poly lstans(ans.begin(),ans.begin()+siz);
    return lstans;
}

Poly operator /(Poly a,Poly b) {
    Poly ans;
    ans.clear();
    int siz=a.size()-b.size()+1;
    reverse(a.begin(),a.end()),reverse(b.begin(),b.end());
    ans=a*inv(b,siz);
    Poly lstans(ans.begin(),ans.begin()+siz);
    reverse(lstans.begin(),lstans.end());
    return lstans;
}
Poly operator %(Poly a,Poly b) {
    Poly ans;
    ans.clear();
    ans=a-a/b*b;
    Poly lstans(ans.begin(),ans.begin()+b.size()-1);
    return lstans;
}

Poly deriv(Poly a) {
    Poly ans;
    ans.clear();
    for(int i=1;i<a.size();++i) ans.push_back(a[i]*i%mod);
    return ans;
}
Poly integ(Poly a) {
    Poly ans;
    ans.clear();
    ans.push_back(0);
    for(int i=0;i<a.size();++i) ans.push_back(a[i]*powinv[i+1]%mod);
    return ans;
}

Poly ln(Poly a,int realsiz=0) {
    Poly ans;
    int siz=(realsiz)?realsiz:a.size();
    ans.clear();
    ans=integ(deriv(a)*inv(a,siz));
    Poly lstans(ans.begin(),ans.begin()+siz);
    return lstans;
}

Poly Exp(Poly a) {
    Poly ans;
    ans.clear();
    int siz=a.size(),bit=0,tot=1;
    while(tot<siz) tot<<=1,++bit;
    a.resize(tot,0);
    ans.push_back(1);
    for(int len=1;len<a.size();len<<=1) {
        Poly tmp(a.begin(),a.begin()+(len<<1));
        Poly tmpp;
        tmpp.clear();
        tmpp.push_back(1);
        tmpp=ans*(tmpp-ln(ans,(len<<1))+tmp);
        ans.clear();
        for(int i=0;i<(len<<1);++i) ans.push_back(tmpp[i]);
    }
    Poly lstans(ans.begin(),ans.begin()+siz);
    return lstans;
}

Poly qpow_poly(Poly a,int b,int realsiz=0) {
    Poly ans;
    int siz=(realsiz)?realsiz:a.size();
    ans=Exp(b*ln(a));
    Poly lstans(ans.begin(),ans.begin()+siz);
    return lstans;
}

Poly sqrt(Poly a,int realsiz=0) {
    Poly ans;
    int siz=(realsiz)?realsiz:a.size();
    int bit=0,tot=1;
    while(tot<siz) tot<<=1,++bit;
    a.resize(tot,0);
    ans.push_back(1);
    for(int len=1;len<a.size();len<<=1) {
        Poly tmp(a.begin(),a.begin()+(len<<1));
        Poly tmpp;
        tmpp.clear();
        tmpp=(ans*ans+tmp)*inv(2*ans,len<<1);
        ans.clear();
        for(int i=0;i<(len<<1);++i) ans.push_back(tmpp[i]);
    }

    Poly lstans(ans.begin(),ans.begin()+siz);
    return lstans;
}

int main() {
    init();
    return 0;
}



Foraino0267
3个月前

很高明的一道题,题解晚点再补。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+50,mod=998244353;
int T;
int n;
int a[N];
int inv[N],mul[N],invmul[N];
void init(int limit=N-50) {
    inv[1]=mul[0]=invmul[0]=1;
    for(int i=2;i<=limit;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    for(int i=1;i<=limit;++i) mul[i]=1ll*mul[i-1]*i%mod,invmul[i]=1ll*invmul[i-1]*inv[i]%mod;
}
int C(int n,int m) {
    return 1ll*mul[n]*invmul[m]%mod*invmul[n-m]%mod;
}
int max(int a,int b) {
    return (a>b)?a:b;
}
int min(int a,int b) {
    return (a<b)?a:b;
}
int count(int x,int y) {
    if(y>n) return 0;
    if(y==n) return 1;
    return (0ll+C(n*2-x-y,n-y)-C(n*2-x-y,n-y-1)+mod)%mod;
}
bitset<N> vis;
int main() {
    init();
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        int maxx=0,cnt_min=0,ans=0;
        vis=0,vis[0]=1;
        for(int i=1;i<=n;++i) {
            if(a[i]>maxx) {
                maxx=a[i];
                ans=(0ll+ans+count(i-1,a[i]+1))%mod;
            }
            else {
                while(vis[cnt_min]) ++cnt_min;
                ans=(0ll+ans+count(i-1,maxx+1))%mod;
                if(a[i]!=cnt_min) break;
            }
            vis[a[i]]=1;
        }
        printf("%d\n",ans);
    }
    return 0;
}



Foraino0267
4个月前

凸包闵可夫斯基和的板子题。

啥是闵可夫斯基和

简单来说就是 $A+B=\{ x+y|x\in A, y\in B \}$。

咋求闵可夫斯基和

发现闵可夫斯基和的凸包就是原图所有边极角排序后顺次连接(比如下图两个蓝色的闵可夫斯基和的凸包就是红色部分)。

vEG9tf.png

本题题解

如果 $A=B+C$,那么 $A-B=C$ 即 $A+(-B)=C$,所以 $B$ 取反求一次闵可夫斯基和然后每次判断 $C$ 在不在凸包中就行了。

代码很短。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read() {
    ll r=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') r=(r<<1)+(r<<3)+(ch^48),ch=getchar();
    return r*f;
}
const int N=1e5+50;
const double pi=acos(-1);
const double eps=1e-8;
struct Point {
    ll x,y;
    Point operator + (const Point &) const;
    Point operator - (const Point &) const;
    Point operator * (const ll &) const;
    bool operator == (const Point &) const;
    void operator += (const Point &) ;
    void operator -= (const Point &) ;
};
Point Point::operator +(const Point &a) const{
    Point b={x+a.x,y+a.y};
    return b;
}
Point Point::operator -(const Point &a) const{
    Point b={x-a.x,y-a.y};
    return b;
}
Point Point::operator *(const ll &a) const{
    Point b={x*a,y*a};
    return b;
}
bool Point::operator ==(const Point &a) const{
    return fabs(x-a.x)<eps&&fabs(y-a.y)<eps;
}
void Point::operator +=(const Point &a) {
    x+=a.x,y+=a.y;
}
void Point::operator -=(const Point &a) {
    x-=a.x,y-=a.y;
}
ll dot(Point a,Point b) {
    return a.x*b.x+a.y*b.y;
}
ll cross(Point a,Point b) {
    return a.x*b.y-b.x*a.y;
}
double get_length(Point a) {
    return sqrt(dot(a,a));
}
double get_angle(Point a,Point b) {
    return acos(dot(a,b)/get_length(a)/get_length(b));
}
double get_polar_angle(Point a){
    Point b={1,0};
    double cos_a=1.*dot(a,b)/get_length(a);
    double sin_a=1.*cross(b,a)/get_length(a);
    if(sin_a>=0) return acos(cos_a);
    else return 2.*pi-acos(cos_a);
}
bool cmp_for_polar_angle(Point a,Point b) {
    return (fabs(get_polar_angle(a)-get_polar_angle(b))<eps)?get_length(a)<get_length(b):get_polar_angle(a)<get_polar_angle(b);
}
bool cmp_for_cross(Point a,Point b) {
    return (cross(a,b)==0)?(get_length(a)<get_length(b)):cross(a,b)>0;
}
bool cmp_for_hull(Point a,Point b) {
    return (a.y==b.y)?(a.x<b.x):(a.y<b.y);
}
bool dot_in_convex(Point p,Point a[],int tot) {
    if(cross(p,a[1])>0||cross(a[tot],p)>0) return 0;
    ll critical_p=lower_bound(a+1,a+tot+1,p,cmp_for_cross)-a-1;
    Point A=p-a[critical_p],B=a[critical_p%tot+1]-a[critical_p];
    return cross(p-a[critical_p],a[critical_p%tot+1]-a[critical_p])<=0;
}
Point st[N];
int tail;
int convex_hull(int tot,Point a[]) {
    sort(a+1,a+tot+1,cmp_for_hull);
    tail=0;
    for(int i=1;i<=tot;++i) {
        while(tail>1&&cross(st[tail]-st[tail-1],a[i]-st[tail-1])<=0) tail--;
        st[++tail]=a[i];
    }
    int tmp=tail;
    for(int i=tot-1;i;--i) {
        while(tail>tmp&&cross(st[tail]-st[tail-1],a[i]-st[tail-1])<=0) tail--;
        st[++tail]=a[i];
    }
    if(tot>1) tail--;
    return tail;
}
Point edge_for_msch[N];
Point ans[N];
int cnt_of_msch;
Point start_p;
int minkowski_sum_of_convex_hull(int tota,Point a[],int totb,Point b[]) {
    cnt_of_msch=0;
    int tmpa=convex_hull(tota,a);
    start_p=st[1];
    for(int i=1;i<=tmpa;++i) edge_for_msch[++cnt_of_msch]=st[i%tmpa+1]-st[i];
    int tmpb=convex_hull(totb,b);
    start_p+=st[1];
    for(int i=1;i<=tmpb;++i) edge_for_msch[++cnt_of_msch]=st[i%tmpb+1]-st[i];
    sort(edge_for_msch+1,edge_for_msch+cnt_of_msch+1,cmp_for_polar_angle);
    ans[1]=start_p;
    for(int i=1;i<cnt_of_msch;++i) ans[i+1]=ans[i]+edge_for_msch[i];
    int tmpans=convex_hull(cnt_of_msch,ans);
    return tmpans;
}
int n,m,q;
Point a[N],b[N],query;
int main() {
    n=(int)read(),m=(int)read(),q=(int)read();
    for(int i=1;i<=n;++i) a[i].x=read(),a[i].y=read();
    for(int i=1;i<=m;++i) b[i].x=read(),b[i].y=read(),b[i].x=-b[i].x,b[i].y=-b[i].y;
    int tot_ans=minkowski_sum_of_convex_hull(n,a,m,b);
    Point tmp=st[1];
    for(int i=1;i<=tot_ans;++i) st[i]-=tmp;
    while(q--) {
        query.x=read(),query.y=read();
        query-=tmp;
        printf("%d\n",dot_in_convex(query,st,tot_ans));
    }
    return 0;
}



Foraino0267
4个月前

式子摘自洛谷用户璀璨星空1的题解(Orz。

这题就是求没有等价点的图的最大边数。

考虑原图没有等价点,则补图也没有等价点,求原图最大边数等价于总边数减求补图最小边数。

$n=1$ 答案显然为 $0$;

$n=2、3$ 答案显然为 $-1$;

$n=4$ 时原图和补图都需要联通,所以边数都至少为 $3$ ,而经过枚举,大小为 $4$ 的树不可能没有对称点,所以答案为 $-1$;

$n=5$ 时原图和补图都需要连通,总边数为 $10$,可能情况有 $4/6$ 或 $5/5$ ,经枚举可以知道不可能不存在对称点,所以答案也为 $-1$;

$n=6$ 时原图和补图都需要连通,总边数为 $15$,$5/10$ 时容易得到五个点的树不可能不存在对称点,而 $6/9$ 时可以构造一个环上链长度为 $1,2,3$ 的基环树,所以答案为 $9$;

$n\ge 7$ 时至少都可以构造一个从中心像三个方向发散长度为 $2,3,n-3$ 的树,所以一定存在答案。

我们贪心考虑一下, $n\ge 7$ 时补图的每个联通块一定都是小于 $n$ 的树构成,不选大小为 $6$ 的基环树的原因是容易证明一定有小于或者等于这种选法的答案。

那么我们求出大小为 $n$ 的无标号无根无对称点树的个数就行了,设这个个数序列为 $U$,考虑能不能通过递推求出 $U$ ,发现由于无根不好求,那就用有根的来求。

设有根无对称点的个数为 $R$ ,考虑讨论重心位置:

1、 $n\bmod 2=1$ 时,重心唯一,减去有子树大于二分之一的情况即 $R_n-\frac{1}{2}\sum_1^{n-1}R_{i}R_{n-i}$;

2、 $n\bmod 2= 0$ 时,除开减去有子树大于二分之一的情况以外,还要除去两棵树互为同构的情况即 $R_n-\frac{1}{2}\sum_1^{n-1}R_{i}R_{n-i}-\frac{1}{2}R_{\frac{n}{2}}$。

快速算出 $R_i$ 即可。

又 $ R_n=\sum_{(\sum_{i=1}^{n-1}(i\times x_i))+1=n}\prod_{i=1}^{n-1}{R_i\choose x_i}$ ,考虑生成函数 $F(x)=x\prod_{i=1}^\infty(1+x^i)^{R_i}$。

两边同时取 $\ln$,得到 $\ln F(x)=\ln x+\sum_{i=1}^\infty (R_i\ln(1+x^i))$;

同时求导,得到 $ \dfrac{F’(x)}{F(x)}=\dfrac1x+\sum_{i=1}^{\infty}(R_i\cdot\dfrac{ix^{i-1}}{1+x^i})$;

所以 $xF’(x)=F(x)+F(x)\sum_{i=1}^{\infty}(R_i\cdot\dfrac{ix^{i}}{1+x^i})$;

对比两边 $x^n$ 的系数,得到:

$ R_n=\dfrac1{n-1}\cdot(\sum_{i=1}^{n-1}(R_{n-i}(\sum_{d|i}(-1)^{\frac id+1}dR_d)))$。

直接算 $R,U$,贪心数数即可。

#include<bits/stdc++.h>
#define LL __int128
const int LEN = 100;
using namespace std;
typedef long long ll;
int T;
LL read() {
    LL val=0,cnt=0;
    char ch=' ';
    while(!('0'<=ch&&ch<='9')) ch=getchar();
    while('0'<=ch&&ch<='9') val=(val<<1)+(val<<3)+(ch-'0'),ch=getchar(),++cnt;
    if(cnt>=100) return 0;
    return val;
}
void write(LL val) {
    if(val==0) {
        printf("0\n");
        return;
    }
    int tmp=val;
    stack<char> st;
    while(!st.empty()) st.pop();
    while(tmp>=1) st.push((tmp%10)+'0'),tmp/=10;
    while(!st.empty()) printf("%c",st.top()),st.pop();
    printf("\n");
}
LL n,r[105],u[105];
const LL mod=1e9+7;
int main() {
    LL a,b;
    r[1]=r[2]=1;
    for(int i=3;i<=100;++i) {
        for(int j=1;j<i;++j) {
            LL anss=0;
            int sqt=sqrt(j);
            for(int l=1;l<=sqt;++l) {
                if(j%l) continue;
                anss+=((j/l)&1?1:-1)*l*r[l];
                if(j/l!=l) anss+=(l&1?1:-1)*(j/l)*r[j/l];
            }
            LL tmp=r[i-j]*anss;
            r[i]+=tmp;
        }
        r[i]/=i-1;
    }
    for(int i=1;i<=100;++i) {
        u[i]=r[i]*2;
        for(int j=1;j<i;++j) u[i]-=r[j]*r[i-j];
        if(!(i&1)) u[i]-=r[i>>1];
        u[i]/=2;
    }
    scanf("%d",&T);
    while(T--) {
        n=read();
        LL tmpn=n;
        if(n==1) puts("0");
        else if(n>=2&&n<=5) puts("-1");
        else if(n==6) puts("9");
        else if(n==0) puts("155132763");
        else {
            LL ans=0;
            for(int i=1;i<=100;++i) {
                LL tmpi=i;
                if(tmpn>=(tmpi*u[i])) tmpn-=(tmpi*u[i]),ans+=u[i];
                else {
                    ans+=(tmpn/i);
                    break;
                }
            }
            write(((ans+n*(n-3)/2)%mod+mod)%mod);
        }
    }
    return 0;
}



Foraino0267
4个月前

很牛的一道题啊,思路部分摘自 command_block 的博客。

首先 k-th Min-Max 容斥,这玩意儿同样是在期望条件下成立的,代公式得到 $ans=\sum_{T\subset S} (-1)^{|T|-k}{{|T|-1}\choose{k-1}}E(min(T))$,$E(min(T))$ 的结果非常显然,就是$\frac{m}{\sum_{i\in T}p_i}$。

但是直接 $2^n$ 枚举子集肯定会寄,然后发现值域居然给了个范围,考虑根据值 DP ,考虑设 $f_{i,j,k}$ 为前 $i$ 个里选了 $j$ 个,$\sum p_i$ 为 $k$,第一维可以滚掉,但是 $n^2m$ 时间复杂度仍然会寄。

然后观察到还有什么奇怪的范围可能作为状态数出现,发现 $k$(因为是第 $k$ 大,所以这里的 $k$ 就是原题的 $n-k$)很小,考虑能不能搞个跟 $k$ 相关的 DP 优化掉一个 $n$(即不记录选择的个数),我们考虑剩下的那一个关于集合大小的系数,加入一个数后会得到 $(-1)^{|T|-k+1}{{|T|}\choose{k-1}}$,关键是后面那坨组合数不好搞,强行把它拆开成 $(-1)^{|T|-k+1}{{|T|}\choose{k-1}}=(-1)^{|T|-k-1}{{|T|}\choose{k-2}}-(-1)^{|T|-k}{{|T|-1}\choose{k-1}}$,这样记录一个 $k$ 就行了,容易得到 DP 式子 $f_{i,j,k}+=f_{i-1,j,k}$,$f_{i,j+p_i,k}+=f_{i-1,j,k-1}-f_{i-1,j,k}$,第一维还是可以滚掉。

代码很短,难在思维。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int M=100005,K=15,N=1005;
int qpow(int a,int b) {
    int ans=1;
    while(b) {
        if(b&1) ans=1ll*ans*a%mod;
        a=1ll*a*a%mod,b>>=1;
    }
    return ans;
}
int f[2][M][K];
int n,m,k;
int p[N];
int ans;
int main() {
    scanf("%d%d%d",&n,&k,&m);
    k=n-k+1;
    for(int i=1;i<=n;++i) scanf("%d",&p[i]);
    f[0][0][0]=1;
    for(int i=1;i<=n;++i){
        for(int j=0;j<=m;++j)
            for(int l=0;l<=k;++l) f[i&1][j][l]=f[i&1^1][j][l];
        if(!p[i]) continue;
        for(int j=0;j<=m-p[i];++j)
            for(int l=1;l<=k;++l) f[i&1][j+p[i]][l]=(1ll*f[i&1][j+p[i]][l]+f[i&1^1][j][l-1]-f[i&1^1][j][l]+mod)%mod;
    }
    for(int i=1;i<=m;++i) ans=(ans+1ll*f[n&1][i][k]*qpow(i,mod-2)%mod*m%mod+mod)%mod;
    printf("%d\n",ans);
    return 0;
}


新鲜事 原文

Foraino0267
4个月前
天依生日快乐!



Foraino0267
5个月前

$Min-Max$ 容斥定理在期望条件下也是成立的。
直接套用 $Min-Max$ 容斥。
子集和就直接用 $or$ 的 $DWT$ 就好了。
代码巨短。

#include<bits/stdc++.h>
using namespace std;
const int N=21;
const double eps=1e-9;
int n;
double a[1<<N],ans;
int count1(int x) {
    int ans=0;
    while(x) ans+=x&1,x>>=1;
    return ans;
}
int main() {
    scanf("%d",&n);
    for(int i=0;i<1<<n;i++) scanf("%lf",&a[i]);
    for(int mid=1;mid<1<<n;mid<<=1)
        for(int i=0;i<1<<n;i+=mid<<1)
            for(int j=0;j<mid;++j) a[i+j+mid]+=a[i+j];
    for(int i=0;i<(1<<n)-1;++i) {
        if(1-a[i]<eps) {
            puts("INF");
            return 0;
        }
        a[i]=1./(1-a[i]);
    }
    for(int i=1;i<1<<n;++i) ans+=((count1(i)&1)?1.:-1.)*a[i^((1<<n)-1)];
    printf("%.12lf",ans);
    return 0;
}



Foraino0267
5个月前

数据范围看错了,事实上数据范围允许一个很简单的容斥。
推广辗转相除版高斯消元,废除取模!!!!1

#include<bits/stdc++.h>
using namespace std;
const int N=20,M=250;
const int mod=1e9+7;
int n;
int e[N][N],d[N][N];
bool vis[N];
int lastans;
vector<pair<int,int> > v[N];
int delt(int a[N][N],int sz) {
    int ans=1;
    for(int i=1;i<=sz;++i) {
        for(int j=i+1;j<=sz;++j) {
            while(a[i][i]) {
                int div=a[j][i]/a[i][i];
                for(int l=i;l<n;++l) a[j][l]=(a[j][l]-1ll*a[i][l]*div%mod+mod)%mod;
                swap(a[i],a[j]);
                ans=-ans;
            }
            swap(a[i],a[j]);
            ans=-ans;
        }
    }
    for(int i=1;i<=sz;++i) ans=(1ll*ans*a[i][i])%mod;
    return (ans+mod)%mod;
}
void dfs(int t,int num) {
    if(t>=n) {
        memset(e,0,sizeof(e));
        memset(d,0,sizeof(d));
        for(int i=1;i<n;++i) {
            if(vis[i]) {
                int tmpm=v[i].size();
                for(int j=0;j<v[i].size();++j) {
                    int tmpu=v[i][j].first,tmpv=v[i][j].second;
                    d[tmpu][tmpu]++;
                    d[tmpv][tmpv]++;
                    e[tmpu][tmpv]++;
                    e[tmpv][tmpu]++;
                }
            }
        }
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j) e[i][j]=(d[i][j]-e[i][j]+mod)%mod;
        lastans=(1ll*lastans+delt(e,n-1)*(1-((((n-1)&1)^(num&1))<<1))%mod+mod)%mod;
        return;
    }
    dfs(t+1,num);
    vis[t]=1;
    dfs(t+1,num+1);
    vis[t]=0;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<n;++i){
        int m;
        scanf("%d",&m);
        for(int j=1;j<=m;++j) {
            int tmpu,tmpv;
            scanf("%d%d",&tmpu,&tmpv);
            v[i].push_back(make_pair(tmpu,tmpv));
        }
    }
    dfs(1,0);
    printf("%d\n",lastans);
    return 0;
}


新鲜事 原文

Foraino0267
5个月前
NOI推迟了,好! 同步赛取消了,€€£你【】什么时候【】啊??!