目录

• H Wheel of Fortune
• F Shannon Switching Game
• I Yet Another FFT Problem

H Wheel of Fortune

题目

​ 两个人在打炉石。双方英雄血量分别为A和B，并且双方各有7个随从，血量为ai和bi。

有一个操作，每次从场上的人中随机选择一个血量>0的人攻击，该人血量减10。A和B谁的血量先<=0，谁输。问A赢的概率。

分析

​ 通过观察可以发现，对随从的攻击不影响最后的结果。所以只用考虑两个英雄的血量。

A获胜时，已经进行了$x(b\le x\le b+a-1)x(b\backslash leq\; x\; \backslash leq\; b+a-1)$次攻击，且最后一次攻击对象为B。

对应概率$P(x)=C_{x-1}^{b-1}\mathrm{/}{2}^{x-1}\ast 1\mathrm{/}2P(x)=C\_\{x-1\}^\{b-1\}/2^\{x-1\}*1/2$,则获胜概率为$P(A)={\sum }_{x=b}^{b+a-1}P(x)P(A)=\backslash sum\_\{x=b\}^\{b+a-1\}P(x)$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=1e7+10,M=1e6+5;

int n,m,k,p;
int fac[N],inv[N];

ll qsm(ll a,ll b) {
    ll ans=1;
    while(b) {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

void init(int n) {
    fac[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=qsm(fac[n],mod-2);
    for(int i=n-1;i>=0;i--) inv[i]=1ll*(i+1)*inv[i+1]%mod;
}

int C(int a,int b) {
    return 1ll*fac[a]*inv[b]%mod*inv[a-b]%mod;
}

void solve() {
    int a,b,x;
    cin>>a;
    for(int i=2;i<=8;i++) cin>>x;
    cin>>b;
    for(int i=2;i<=8;i++) cin>>x;
    a=(a+10-1)/10; b=(b+10-1)/10;
    init(a+b);
    ll ans=0;
    for(int i=b;i<=b+a-1;i++) {
        ans=(ans+1ll*C(i-1,b-1)*qsm(qsm(2,i),mod-2)%mod)%mod;
    }
    cout<<ans<<endl;
}

int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; //cin>>T;
	while(T--) {
        //cout<<"Case#"<<T<<":\n";
        solve();
	}
	return 0;
}

F Shannon Switching Game

题目

​ 给定一个无向图，起点s终点t，两个玩家Join Player和Cut Player轮流行动，Cut Player先手。

​ C每次可以删除一条当前位置相邻的边；J每次可以沿一条边移动。

​ 如果物品在某刻被移动到t，则J获胜，否则Cut Player获胜，求双方最优策略下的胜者。

分析

​ 博弈论。

​ 1、已知终点为必胜态。

​ 2、若改点有两条边连接必胜态，该点也为必胜态。

​ 从终点进行bfs，遍历出所有的必胜态。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=1e2+10,M=1e6+5;

int n,m,k,p,s,t;
int g[N][N],num[N];
bool st[N];

void bfs() {
    queue<int> q;
    q.push(t); st[t]=true;
    while(q.size()) {
        int x=q.front(); q.pop();
        for(int i=1;i<=n;i++) {
            if(st[i]) continue;
            num[i]+=g[x][i];
            if(num[i]>=2) {
                q.push(i); st[i]=true;
            }
        }
    }
}

void solve() {
    cin>>n>>m>>s>>t;
    int x,y;
    memset(st,0,sizeof(st));
    memset(g,0,sizeof(g));
    memset(num,0,sizeof(num));
    for(int i=1;i<=m;i++) {
        cin>>x>>y;
        g[x][y]++; g[y][x]++;
    }
    bfs();
    if(num[s]>1) cout<<"Join Player\n";
    else cout<<"Cut Player\n";
}

int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; cin>>T;
	while(T--) {
        //cout<<"Case#"<<T<<":\n";
        solve();
	}
	return 0;
}

I Yet Another FFT Problem

题目

​ 给定长度为n的数组a,长度为m的数组b,是否存在$\mathrm{\mid }{a}_i-a_j\mathrm{\mid }=\mathrm{\mid }{b}_k-b_l\mathrm{\mid }(i\mathrm{\ne }j,k\mathrm{\ne }l)|a\_i-a\_j|=|b\_k-b\_l|\; (i\backslash neq\; j,k\backslash neq\; l)$。存在输出，不存在输出-1。

分析

​ 去绝对值有，$a_i+b_l=a_j+b_{k}a\_i+b\_l=a\_j+b\_k$，由于数据范围为$10^{7}10^7$，所以$a_i+b_j\le 2\ast 10^{7}a\_i+b\_j\backslash leq\; 2*10^7$，由鸽巢原理知，最多枚举$2\ast 10^{7}2*10^7$，就会出现相同的和。同时，对$a_i=a_j,b_k=b_{l}a\_i=a\_j,b\_k=b\_l$情况进行特殊处理。将数组去重，则不存在$a_i+b_j=a_i+b_{l}a\_i+b\_j=a\_i+b\_l$，两重循环即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;
const int mod=998244353;
const int N=1e6+10,M=1e7+5;

int n,m,k,p;
int a[N],b[N];
int fa[M],fb[M];

void solve() {
    cin>>n>>m;
    vector<int> pa,pb;
    int ans[2][2]={{0,0},{0,0}};
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        if(fa[a[i]]==0) {
            pa.push_back(i); fa[a[i]]=i;
        } else {
            ans[0][0]=fa[a[i]]; ans[0][1]=i;
        }
    }
    for(int i=1;i<=m;i++) {
        cin>>b[i];
        if(fb[b[i]]==0) {
            pb.push_back(i); fb[b[i]]=i;
        } else {
            ans[1][0]=fb[b[i]]; ans[1][1]=i;
        }
    }
    if(ans[0][0]&&ans[1][0]) {
        printf("%d %d %d %d\n",ans[0][0],ans[0][1],ans[1][0],ans[1][1]);
        return;
    }
    vector<array<int, 2>> f(2 * M, {0,0});
    for(int i:pa) {
        for(int j:pb) {
            int t=a[i]+b[j];
            if(f[t][0]==0) {
                f[t]={i,j};
            } else {
                printf("%d %d %d %d\n",f[t][0],i,j,f[t][1]);
                return;
            }
        }
    }
    printf("-1\n");
}

int main(){
    //freopen("data.in","r",stdin);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int T=1; //cin>>T;
	while(T--) {
        //cout<<"Case#"<<T<<":\n";
        solve();
	}
	return 0;
}