A题
inline ll pw(ll n,ll m){ll r=1;for(;m;m>>=1,n=n*n%MOD)if(m&1)r=r*n%MOD;return r;}
const int N=1e6+11;
int n,m;
ll fac[N],fai[N];
void init(){
fac[0]=1;
rep(i,1,n)fac[i]=fac[i-1]*i%MOD;
fai[n]=pw(fac[n],MOD-2);
per(i,0,n-1)fai[i]=fai[i+1]*(i+1)%MOD;
}
I ll C(int n,int m){return fac[n]*fai[n-m]%MOD*fai[m]%MOD;}
int main(){
in,n,m;
if(n<m)return puts("0"),0;
init();
ll ans=pw(m,n);
rep(i,1,m){
ans+=(i%2?-1:1)*C(m,i)*pw(m-i,n)%MOD;
}
ans=(ans%MOD+MOD)%MOD;
out,ans,'
';
}
C题
#include<bits/stdc++.h>
#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lf else if
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> Vi;
int IN(){
int c,f,x;
while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}
const int N=20;
const int p=998244353;
struct Edge{
int y,nxt;
} E[N*N];
int f[1<<N][N],las[N],mx[1<<N],Lg[1<<N],A[N][N];
int n,m,x,y,ans;
inline void upd(int &x,int y){
x=(x+y>=p?x+y-p:x+y);
}
int main(){
For(i,0,N) Lg[1<<i]=i;
For(t,0,1<<N){
For(i,0,N) if (t>>i&1) mx[t]=i;
}
n=IN();m=IN();
For(i,0,m){
x=IN()-1,y=IN()-1;
A[x][y]=1;
}
For(i,0,n) f[1<<i][i]=1;
For(t,0,1<<n) For(x,0,n) if (f[t][x]){
for (int w=~t&(1<<n)-1;w;w^=w&-w){
int y=Lg[w&-w];
if (y<mx[t]&&A[x][y]||y>mx[t]&&A[x][mx[t]]){
upd(f[t|1<<y][y],f[t][x]);
}
}
if (A[x][mx[t]]){
if (t==(1<<n)-1) upd(ans,f[t][x]);
}
}
printf("%d
",ans);
}
以下暂时是mcfx给的代码
顺序为BDEF
const int N=500007;
std::vector<pii>p[N],q[N];
pii e[N];
std::vector<int>u[N];
int n,m,ans[N],f[N],g[233];
inline void modify(int x,int v)
{
for(;x<n;x+=x&-x)repr(f[x],v);
}
inline int query(int x)
{
int r=0;
for(;x;x^=x&-x)repr(r,f[x]);
return r;
}
int main()
{
in,n;
fo1(i,n-1)
{
int x,y;
in,x,y;
e[i]=mp(x,y);
p[x].pb(mp(i,y));
}
in,m;
fo1(i,m)
{
int x,y;
in,x,y;
repl(x,n-1);
repl(y,n-1);
q[x].pb(mp(y,i));
}
mset(g,0x7f);
fo1(i,n)std::sort(p[i].begin(),p[i].end(),std::greater<pii>());
fo1(i,n)u[i].pb(1);
ll ans=0;
fd1(i,n-1)
{
//out,i,'
';
int x=e[i].xx,y=e[i].yy,t=u[y].size()+1;
g[0]=1;
fo0(k,u[y].size())g[k+1]=max(u[y][k],i);
//fo0(j,10)out,g[j],' ';out,'
';
fo0(j,u[x].size())fo0(k,u[y].size())repl(g[j+k+1],max(max(u[x][j],u[y][k]),i));
//fo0(j,10)out,g[j],' ';out,'
';
for(int j=0;g[j]!=0x7f7f7f7f;g[j++]=0x7f7f7f7f)
modify(g[j],j);
fo0(k,u[y].size())
{
if(u[x].size()==k+1)u[x].pb(max(u[y][k],i));
else repl(u[x][k+1],max(u[y][k],i));
}
//foe(j,q[i])ans[j->yy]=query(j->xx);
foe(j,q[i])ans+=query(j->xx);
}
out,ans,'
';
//fo1(i,m)out,ans[i],'
';
}
D
const int N=200007,P=1000000007;
int n,l[N],r[N],po[N];
std::vector<int>s[N],t[N];
struct node
{
int cnt,sum,tag;
node(){tag=1;}
}sl[1<<19],sr[1<<19];
inline void pu(node*s,int x)
{
s[x].sum=(s[x<<1].sum+s[x<<1|1].sum)%P;
s[x].cnt=s[x<<1].cnt+s[x<<1|1].cnt;
}
inline void st(node*s,int x,int t)
{
s[x].sum=(ll)s[x].sum*t%P;
s[x].tag=(ll)s[x].tag*t%P;
}
inline void pd(node*s,int x)
{
if(s[x].tag!=1)
{
st(s,x<<1,s[x].tag);
st(s,x<<1|1,s[x].tag);
s[x].tag=1;
}
}
inline void mul(node*s,int x,int l,int r,int ql,int qr,int v)
{
if(ql>qr)return;
if(l>=ql&&r<=qr)return st(s,x,v);
int t=(l+r)>>1;pd(s,x);
if(ql<=t)mul(s,x<<1,l,t,ql,qr,v);
if(qr>t)mul(s,x<<1|1,t+1,r,ql,qr,v);
pu(s,x);
}
inline int cnt(node*s,int x,int l,int r,int ql,int qr)
{
if(ql>qr)return 0;
if(l>=ql&&r<=qr)return s[x].cnt;
int t=(l+r)>>1,c=0;
if(ql<=t)c+=cnt(s,x<<1,l,t,ql,qr);
if(qr>t)c+=cnt(s,x<<1|1,t+1,r,ql,qr);
return c;
}
inline void modify(node*s,int x,int l,int r,int p,int v,int c)
{
if(l==r)
{
(s[x].sum+=v)%=P;
s[x].cnt+=c;
}
else
{
int t=(l+r)>>1;pd(s,x);
if(p<=t)modify(s,x<<1,l,t,p,v,c);
else modify(s,x<<1|1,t+1,r,p,v,c);
pu(s,x);
}
}
inline void mod(node*s,int x,int f,bool g)
{
if(f>0)
{
mul(s,1,1,n*2,x,n*2,2);
int c=cnt(s,1,1,n*2,1,x-1);
if(g)modify(s,1,1,n*2,x,(ll)po[c]*(n*2-x+1)%P,1);
else modify(s,1,1,n*2,x,(ll)po[c]*x%P,1);
}
else
{
int c=cnt(s,1,1,n*2,1,x-1);
if(g)modify(s,1,1,n*2,x,P-(ll)po[c]*(n*2-x+1)%P,-1);
else modify(s,1,1,n*2,x,P-(ll)po[c]*x%P,-1);
mul(s,1,1,n*2,x,n*2,(P+1)/2);
}
}
int main()
{
po[0]=1;
fo1(i,N-1)po[i]=po[i-1]*2%P;
in,n;
fo1(i,n)in,l[i],r[i];
fo1(i,n)s[l[i]].pb(i);
fo1(i,n)t[++r[i]].pb(i);
int ans=0;
fo1(i,n*2)
{
foe(j,s[i])mod(sl,n*2-l[*j]+1,1,1),mod(sr,r[*j],1,0);
foe(j,t[i])mod(sl,n*2-l[*j]+1,-1,1),mod(sr,r[*j],-1,0);
ans=((ll)ans+sr[1].sum+P-sl[1].sum)%P;
}
out,ans,'
';
}
E
typedef unsigned char uc;
const int N=1<<17;
uc a[N],b[N],c[N],f[1<<8][1<<8];
int main()
{
int n,m,x=(1<<20)-1;
in,n,m;
a[0]=1;fo1(i,n)a[i>>3]|=((char)in&1)<<(i&7);
b[x>>3]=1<<7;fo1(i,m)b[(x^i)>>3]|=((char)in&1)<<((x^i)&7);
fo0(i,1<<8)fo0(j,1<<8)fo0(k,8)
{
uc t=0;
fo0(u,8)if((u&k)==u)t^=(i>>u)&(j>>(u|(k^7)))&1;
f[i][j]|=t<<k;
}
fo0(i,N)
{
uc t=0;
int v=(N-1)^i;
for(int j=i;;j=(j-1)&i)
{
t^=f[a[j]][b[j|v]];
if(!j)break;
}
c[i]=t;
}
ll ans=0;
fo0(i,1<<20)if(c[i>>3]>>(i&7)&1)ans+=(ll)i*i;
out,ans,'
';
}
F
const int N=100007;
struct data
{
ll lc,rc,fa,ga,fu,gu;
}f[N];
int n,lc[N],rc[N],fa[N],cnt[N],dep[N];
ll tag[N],ans[N];
inline void dfs(int x)
{
bool a=lc[fa[x]]==x,b=lc[fa[fa[x]]]==fa[x];
data t=f[fa[fa[x]]];
if(a&&b)
{
f[x]=(data){-2+t.lc,-1+t.rc,t.rc,2+t.rc,1+t.rc,2+t.rc};
}
else if(!a&&!b)
{
f[x]=(data){-1+t.lc,-2+t.rc,t.lc,2+t.lc,1+t.lc,2+t.lc};
}
else if(!a&&b)
{
f[x]=(data){-1+t.lc,-1+t.rc,t.lc,1+t.rc,t.lc,1+t.rc};
}
else if(a&&!b)
{
f[x]=(data){-1+t.lc,-1+t.rc,t.rc,1+t.lc,t.rc,1+t.lc};
}
if(lc[x])dfs(lc[x]);
if(rc[x])dfs(rc[x]);
cnt[fa[fa[x]]]+=cnt[x];
}
inline void dfs2(int x)
{
tag[lc[x]]+=tag[x];
tag[rc[x]]+=tag[x];
ans[x]+=(ll)dep[x]*(n-1)+tag[x];
dep[lc[x]]=dep[x]+1;
dep[rc[x]]=dep[x]+1;
if(lc[x])dfs2(lc[x]);
if(rc[x])dfs2(rc[x]);
}
int main()
{
in,n;
fo1(i,n)
{
in,lc[i],rc[i];
if(lc[i])fa[lc[i]]=i;
if(rc[i])fa[rc[i]]=i;
}
f[1]=(data){0,0,0,0,0,0};
f[lc[1]]=(data){-1,0,1,0,1,0};
f[rc[1]]=(data){0,-1,1,0,1,0};
fo1(i,n)cnt[i]=1;
if(lc[lc[1]])dfs(lc[lc[1]]);
if(lc[rc[1]])dfs(lc[rc[1]]);
if(rc[lc[1]])dfs(rc[lc[1]]);
if(rc[rc[1]])dfs(rc[rc[1]]);
//fo1(x,n)out,x,':',f[x].lc,' ',f[x].rc,' ',f[x].fa,' ',f[x].ga,' ',f[x].fu,' ',f[x].gu,' ',"cnt=",cnt[x],'
';
fo(i,2,n)
{
tag[lc[i]]+=f[i].lc;
tag[rc[i]]+=f[i].rc;
ans[fa[i]]+=cnt[i]*f[i].fa;
ans[fa[fa[i]]]+=cnt[i]*f[i].ga;
tag[lc[fa[i]]==i?rc[fa[i]]:lc[fa[i]]]+=cnt[i]*f[i].fu;
tag[lc[fa[fa[i]]]==fa[i]?rc[fa[fa[i]]]:lc[fa[fa[i]]]]+=cnt[i]*f[i].gu;
}
//fo1(i,n)out,tag[i],' ';out,'
';
//fo1(i,n)out,ans[i],' ';out,'
';
dfs2(1);
fo1(i,n)out,ans[i]%1000000007,'
';
}