Foraino0267

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

2360

Andy2035

lsz_

ntql
acwing_xyy
GymDarius

yxc的小迷妹1
Eager
Fatin
hansang

xiuzhiyuan

163.com

Foraino0267
2个月前

Foraino0267
2个月前

#include<bits/stdc++.h>
typedef long long ll;
#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();
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;
}
}
}

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
5个月前

#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
6个月前

### 本题题解

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
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() {
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-=tmp;
printf("%d\n",dot_in_convex(query,st,tot_ans));
}
return 0;
}


Foraino0267
6个月前

$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$ 的树，所以一定存在答案。

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_n=\dfrac1{n-1}\cdot(\sum_{i=1}^{n-1}(R_{n-i}(\sum_{d|i}(-1)^{\frac id+1}dR_d)))$。

#include<bits/stdc++.h>
#define LL __int128
const int LEN = 100;
using namespace std;
typedef long long ll;
int T;
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--) {
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
6个月前

#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
6个月前

Foraino0267
6个月前

$Min-Max$ 容斥定理在期望条件下也是成立的。

#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
7个月前

#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
7个月前
NOI推迟了，好！ 同步赛取消了，€€￡你【】什么时候【】啊？？！