省选联测 41

worldvanquisher · 2023-02-27 14:46:12 · 个人记录

看见 T4 直接倒序开题。

冤家路窄

感觉挺显然的，但是似乎大多数人都打挂了。

首先可以转化成计数不合法的。然后分别考虑点和边相遇。点的话就是从 S 过来的时间等于到 T 的时间，边的话是过来和过去的时间有交。方案数是过来的乘过去的再平方。为什么平方？因为是最短路条数，不是两个人走过来的方案数。一条最短路的方案数是过来的乘过去的，两条就是平方。

场上没平方，噶了。那我是小丑。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#define int long long
using namespace std;
const int mod=1000000007;
int n,m,S,T;
struct node{
    int v,w,next;
}edge[400010];
int t,head[100010];
bool vis[100010];
long long dis[100010];
vector<pair<int,long long> >g[2][100010],pre[100010];
void add(int u,int v,int w){
    edge[++t].v=v;edge[t].w=w;edge[t].next=head[u];head[u]=t;
}
struct stu{
    int x;long long w;
    bool operator<(const stu&s)const{
        return w>s.w;
    }
};
void dijkstra(int st){
    priority_queue<stu>q;
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;q.push({st,0});
    while(!q.empty()){
        int x=q.top().x;q.pop();
        if(!vis[x]){
            vis[x]=true;
            for(int i=head[x];i;i=edge[i].next){
                if(dis[edge[i].v]>dis[x]+edge[i].w){
                    dis[edge[i].v]=dis[x]+edge[i].w;
                    pre[edge[i].v].clear();pre[edge[i].v].push_back(make_pair(x,edge[i].w));
                    if(!vis[edge[i].v])q.push({edge[i].v,dis[edge[i].v]});
                }
                else if(dis[edge[i].v]==dis[x]+edge[i].w){
                    pre[edge[i].v].push_back(make_pair(x,edge[i].w));
                }
            }
        }
    }
}
void bfs(){
    queue<int>q;
    q.push(T);
    for(int i=1;i<=n;i++)vis[i]=false;
    vis[T]=true;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(pair<int,long long> p:pre[x]){
            int v=p.first;
            long long w=p.second;
            g[0][v].push_back(make_pair(x,w));g[1][x].push_back(make_pair(v,w));
            if(!vis[v]){
                vis[v]=true;q.push(v);
            }
        }
    }
}
int dp[100010][2],ind[100010];
long long dep[100010][2];
void tuopu(int st,int id){
    queue<int>q;q.push(st);
    for(int i=1;i<=n;i++)ind[i]=0;
    for(int x=1;x<=n;x++){
        for(pair<int,long long> v:g[id][x])ind[v.first]++;
    }
    dp[st][id]=1;dep[st][id]=0;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(pair<int,long long> p:g[id][x]){
            int v=p.first;
            long long w=p.second;
            dp[v][id]=(dp[v][id]+dp[x][id])%mod;
            dep[v][id]=dep[x][id]+w;
            ind[v]--;
            if(!ind[v])q.push(v);
        }
    }
}
signed main(){
    scanf("%lld%lld%lld%lld",&n,&m,&S,&T);
    for(int i=1;i<=m;i++){
        int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);add(v,u,w);
    }
    dijkstra(S);bfs();
    memset(dep,0x3f,sizeof(dep));
    const long long inf=dep[0][0];
    tuopu(S,0);tuopu(T,1);
    int ans=1ll*dp[S][1]*dp[S][1]%mod;
    for(int i=1;i<=n;i++){
        if(dep[i][0]==inf)continue;
        if(dep[i][0]==dep[i][1])ans=(ans-1ll*dp[i][0]*dp[i][1]%mod*dp[i][0]%mod*dp[i][1]%mod+mod)%mod;
        for(pair<int,long long> p:g[0][i]){
            int v=p.first;long long w=p.second;
            if(dep[i][0]+w>dep[v][1]&&dep[v][1]+w>dep[i][0])ans=(ans-1ll*dp[i][0]*dp[v][1]%mod*dp[i][0]%mod*dp[v][1]%mod+mod)%mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

夹克姥爷 win 了 win 了

场上一直以为是不可做题，根本不知道怎么藏信息。最后二十分钟看了眼大样例蒙出结论了，就切了。

首先我们大眼观察大样例可以发现最后边是一堆 0 跟着一个 n。合理猜测答案是 n!+n。它是对的。

joke3579 跟我说道了一下这玩意怎么推出来的。排列藏信息可以康托展开。那考虑除去给的 k-1 个数外的 n-k+1 个数，然后 Alice 的 k 个数可以表示 k! 内的数。所以 n-k+1\le k!，就是 n\le k!+k-1。可行性不会证。原先的证明被 H_Kaguya 车掉了。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
int a[1000010];
void mul(int num){
    int x=0;
    for(int i=1;i<=a[0];i++){
        a[i]=a[i]*num+x;
        x=a[i]/10;a[i]%=10;
    }
    while(x){
        a[++a[0]]=x%10;x/=10;
    }
}
void add(int num){
    int x=0;a[1]+=num;
    for(int i=1;i<=a[0];i++){
        a[i]+=x;
        x=a[i]/10;a[i]%=10;
    }
    while(x){
        a[++a[0]]=x%10;x/=10;
    }
}
int main(){
    scanf("%d",&n);
    a[0]=a[1]=1;
    for(int i=1;i<=n;i++)mul(i);
    add(n);
    for(int i=a[0];i>=1;i--)printf("%d",a[i]);puts("");
    return 0;
}

39 与 93

一个 dp 是设 dp_{i,j,k} 为前 i 堆扔掉的 \bmod s=j，剩下的异或和为 k 的方案数。首先可以把 i 压掉。然后发现暴力 dp 是 O(n^2) 的，于是我们把 a 从小到大排序，那么对于第 i 堆，前面的所有异或起来的最大值一定不超过 2i。那么每个位置预处理这个阈值，每次 dp 在这个阈值范围内扫即可，复杂度大概是差不多 O(\sum a_i)。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod=1000000007;
int n,s,a[500010],dp[10][1<<20],lg[1000010],f[1<<20];
int main(){
    freopen("stone.in","r",stdin);
    freopen("stone.out","w",stdout);
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    int ret=1;
    for(int i=1;i<=1000000;i++){
        if(ret<i)ret=ret<<1|1;
        lg[i]=ret;
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=lg[a[i]];j++)f[j]=dp[s-1][j];
        for(int j=s-1;j>=1;j--){
            for(int k=0;k<=lg[a[i]];k++)dp[j][k]=(dp[j][k]+dp[j-1][k^a[i]])%mod;
        }
        for(int k=0;k<=lg[a[i]];k++)dp[0][k]=(dp[0][k]+f[k^a[i]])%mod;
    }
    if(n%s==0)dp[n%s][0]--;
    (dp[n%s][0]+=mod)%=mod;
    printf("%d\n",dp[n%s][0]);
    return 0;
}

Zbox 的刷题 I

一个和题解不一样的推法。赛时倒序开题，差不多快九点半就开完了。

显然我们可以把 a,b 拆开分别算贡献。然后我们可以列出来一个显然的柿子：设 f_i 是 i 道题期望多少轮结束，那么