模拟赛2022.11.21
A.对于每一种灯的颜色1~m，可以求出这个颜色第一次在所有路灯中同时出现的时间，设其为x，则x满足
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7;
int mul(int a,int b,int p) {
int res=0;
while(b) {
if(b&1) res=(res+a)%p;
b>>=1;
a=(a+a)%p;
}
return res;
}
int exgcd(int a,int b,int &x,int &y) {
if(!b) {
x=1,y=0;
return a;
}
int g=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return g;
}
int excrt(int n,int *a,int *b) {//x=b(mod a)
int x,y,k;
int M=a[1],ans=b[1];
for(int i=2; i<=n; i++) {
int tb=M,ta=a[i],tc=(b[i]-ans%ta+ta)%ta;
int g=exgcd(tb,ta,x,y);
int ag=ta/g;
if(tc%g!=0) return -1;
//int tmp=tc/g;
//x=x*tmp%ag;
x=mul(x,tc/g,ag);
ans+=x*M;
M*=ag;
ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
int n,m,l,r,t,s[N],st[N];
vector <int> p[N],tst[N];
int solve(int x){
int ans=0;
for(int i=1;i<=m;i++){//x=st(mod s)
if(tst[i].size()<n) continue;
int top=0;
for(auto v : tst[i]) st[++top]=v;
int y=excrt(n,s,st);
if(y==-1 || y>x) continue;
int k=(x-y)/t;
ans+=k+1;
}
return ans;
}
int lcm(int x,int y){
return x/__gcd(x,y)*y;
}
signed main() {
freopen("walk.in","r",stdin);
freopen("walk.out","w",stdout);
cin >> n >> m >> l >> r;
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
t=(t==0 ? s[i] : lcm(t,s[i]));
for(int j=1,x;j<=s[i];j++){
scanf("%d",&x);
p[i].push_back(x);
tst[x].push_back(j);
}
getchar();
}
//cout << solve(l-1);
int f1=solve(r);
int f2=solve(l-1);
cout << f1-f2;
return 0;
}
/*
3 4 1 10
4 1 2 3 4
3 1 2 3
2 1 2
*/B.设dp[i]表示处理完前i个质数的答案。
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
unsigned ycy1106=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(ycy1106);
const int N=1e6+7,mod=998244353;
int m,n,a[N],b[N],dp[N];
int ksm(int a,int b,int c){
int res=1;
while(b){
if(b&1) res=res*a%c;
a=a*a%c;
b>>=1;
}
return res;
}
int phi(int n){
int res,x;
res=x=n;
for(int i=2;i*i<=x;i++){
if(x%i!=0) continue;
res=res/i*(i-1);
while(x%i==0) x/=i;
}
if(x>1) res=res/x*(x-1);
return res;
}
inline int read(){
int k=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
k=k*10+ch-'0';
ch=getchar();
}
return k*f;
}
int phin;
signed main()
{
freopen("air.in","r",stdin);
freopen("air.out","w",stdout);
cin >> m >> n;
int phip=phi(mod);
for(int i=1;i<=m;i++) a[i]=read();
for(int i=1;i<=m;i++) b[i]=read();
dp[0]=1;
if(n>=phip){
for(int i=1;i<=m;i++){
if(a[i]==b[i]) dp[i]=dp[i-1];
else{
int del=ksm(b[i]-a[i]+1,n%phip+phip,mod)-(2*ksm(b[i]-a[i],n%phip+phip,mod)-ksm(b[i]-a[i]-1,n%phip+phip,mod));
del=(del%mod+mod)%mod;
dp[i]=dp[i-1]*del%mod;
}
}
}
else{
for(int i=1;i<=m;i++){
if(a[i]==b[i]) dp[i]=dp[i-1];
else{
int del=ksm(b[i]-a[i]+1,n,mod)-(2*ksm(b[i]-a[i],n,mod)-ksm(b[i]-a[i]-1,n,mod));
del=(del%mod+mod)%mod;
dp[i]=dp[i-1]*del%mod;
}
}
}
cout << dp[m];
return 0;
}
/*
2 5
1 1
2 3
*/C.大力推式子
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
unsigned ycy1106=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(ycy1106);
const int N=2e7+7;
ll p;
int jc[N],ijc[N];
int ksm(int a,int b,int c){
int res=1;
while(b){
if(b&1) res=1ll*res*a%c;
a=1ll*a*a%c;
b>>=1;
}
return res;
}
int C(int x,int y){
if(x<y || x<0 || y<0) return 0;
return 1ll*jc[x]*ijc[y]%p*ijc[x-y]%p;
}
int lucas(ll x,ll y){
if(x<p && y<p) return C(x,y);
return 1ll*C(x%p,y%p)*lucas(x/p,y/p)%p;
}
int upd(int x,int y){
ll res=x+y;
if(res>=p) res-=p;
return res;
}
int f(ll n,ll m){
if(n<p && m<p){
int ans=0;
for(int i=0;i<=m;i++) ans=upd(ans,lucas(n,i));
return ans;
}
int tn=n%p;
ll ans=0;
int tc=lucas(n/p,m/p);
int tf=f(n/p,m/p);
for(int i=0;i<=min(m,p-1);i++){
if(i<=m%p) ans=upd(ans,1ll*lucas(tn,i)*tf%p);
else ans=upd(ans,1ll*lucas(tn,i)*(tf-tc+p)%p);
}
return ans;
}
int n,m;
signed main()
{
freopen("dimension.in","r",stdin);
freopen("dimension.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&p);
jc[0]=ijc[0]=1;
for(int i=1;i<=p-1;i++) jc[i]=1ll*jc[i-1]*i%p;
ijc[p-1]=ksm(jc[p-1],p-2,p);
for(int i=p-2;i>=1;i--) ijc[i]=1ll*(i+1)*ijc[i+1]%p;
cout << (f(n+1,m+1)-1+p)%p;
return 0;
}
D.一个假的期望，先按a降序枚举点i，其贡献为目前的（sumdep+dep[i]×a大于它的点数-2×它到根的路径上1的个数）×（m-i），之后再把1~i路径上的点+1即可。最后分母是n×(n-1)。
// ubsan: undefined
// accoders
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
unsigned ycy1106=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(ycy1106);
const int N=8e5+7,mod=998244353;
int n,m,ans,sumdep,now,a[N],dep[N],f[N],dfn[N],cnt,top[N],siz[N],son[N];
basic_string <int> c[N],e[N];
struct node{
int l,r,sum,tag;
}t[N<<2];
void dfs1(int u,int fa){
f[u]=fa;
dep[u]=dep[fa]+1;
siz[u]=1;
for(auto v : e[u]){
if(v==fa) continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int tp){
top[u]=tp;
dfn[u]=++cnt;
if(son[u]) dfs2(son[u],tp);
for(auto v : e[u])
if(v!=f[u] && v!=son[u])
dfs2(v,v);
}
void pushup(int p){
t[p].sum=(t[p<<1].sum+t[p<<1|1].sum)%mod;
}
void pushdown(int p){
if(t[p].tag){
t[p<<1].sum=(t[p<<1].sum+t[p].tag*(t[p<<1].r-t[p<<1].l+1))%mod;
t[p<<1|1].sum=(t[p<<1|1].sum+t[p].tag*(t[p<<1|1].r-t[p<<1|1].l+1))%mod;
t[p<<1].tag=(t[p<<1].tag+t[p].tag)%mod;
t[p<<1|1].tag=(t[p<<1|1].tag+t[p].tag)%mod;
t[p].tag=0;
}
}
void build(int p,int l,int r){
t[p].l=l,t[p].r=r;
if(l==r) return ;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
pushup(p);
}
void change(int p,int l,int r,int d){
if(l<=t[p].l && t[p].r<=r){
t[p].sum=(t[p].sum+d*(t[p].r-t[p].l+1)%mod)%mod;
t[p].tag=(t[p].tag+d)%mod;
return ;
}
pushdown(p);
int mid=t[p].l+t[p].r>>1;
if(l<=mid) change(p<<1,l,r,d);
if(r>mid) change(p<<1|1,l,r,d);
pushup(p);
}
int ask(int p,int l,int r){
if(l<=t[p].l && t[p].r<=r) return t[p].sum;
pushdown(p);
int mid=t[p].l+t[p].r>>1;
if(r<=mid) return ask(p<<1,l,r);
else if(l>mid) return ask(p<<1|1,l,r);
else return ask(p<<1,l,r)+ask(p<<1|1,l,r);
}
void change_on_tree(int x,int y,int d){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
change(1,dfn[top[x]],dfn[x],d);
x=f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
change(1,dfn[x],dfn[y],d);
}
int ask_on_tree(int x,int y){
int res=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=(res+ask(1,dfn[top[x]],dfn[x]))%mod;
x=f[top[x]];
}
if(dep[x]>dep[y]) swap(x,y);
res=(res+ask(1,dfn[x],dfn[y]))%mod;
return res;
}
int ksm(int a,int b,int c){
int res=1;
while(b){
if(b&1) res=1ll*res*a%c;
a=1ll*a*a%c;
b>>=1;
}
return res;
}
signed main()
{
freopen("challenge.in","r",stdin);
freopen("challenge.out","w",stdout);
cin >> n >> m;
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
c[a[i]]+=i;
}
for(int i=1,u,v;i<n;i++){
scanf("%lld%lld",&u,&v);
e[u]+=v,e[v]+=u;
}
dfs1(1,1);
dfs2(1,1);
build(1,1,n);
for(int i=m;i>=1;i--){
for(auto v : c[i]){
int f1=(sumdep+1ll*dep[v]*now%mod)%mod;
int f2=2ll*ask_on_tree(1,v)%mod;
int tmp=((f1-f2)%mod+mod)%mod;
ans=(ans+1ll*(m-i)*tmp%mod)%mod;
}
for(auto v : c[i]){
sumdep=(sumdep+dep[v])%mod;
now++;
change_on_tree(v,1,1);
}
}
int t=1ll*n*(n-1)%mod;
cout << 1ll*ans*ksm(t,mod-2,mod)%mod;
return 0;
}
/*
3 3
3 1 2
1 2
1 3
*/