打牌

pypy3 解法, 执行用时: 158ms, 内存消耗: 26916K, 提交时间: 2023-07-01 10:46:25

from functools import lru_cache
from itertools import product

n = int(input())
x = input() # 有 2 张牌一样的情况下，从中随机挑选
y = input()
z = input()
mod = 10**9 + 7
# invs = [pow(i, mod-2, mod) for i in range(n+1)]


def fraction(a, b, mod=mod):
    # return a*invs[b] % mod
    return (a * pow(b, mod-2, mod)) % mod

win = list(sorted(list('win')))
def has_win(x):
    return all(x[i] == win[i] for i in range(3))

@lru_cache(None)
def h(x, y, z, n):
    x, y, z = map(list, [x, y, z])
    if has_win(x):
        return 1
    if has_win(y) or has_win(z):
        return 0
    if n==0:
        return int(has_win(x))
    # 确定随机抽取的下标
    if x[0]==x[1] and x[1]!=x[2]:
        xis = [0, 1]
    elif x[0]!=x[1] and x[1]==x[2]:
        xis = [1, 2]
    else:
        xis = [0, 1, 2]
    yis = zis = [0, 1, 2]
    res = 0
    total = len(xis)*len(yis)*len(zis)
    for xi, yi, zi in product(xis, yis, zis):
        # 拷贝
        xc = x[::] # copy
        yc = y[::]
        zc = z[::]
        # 获取选取的牌
        x_ = xc[xi]
        y_ = yc[yi]
        z_ = zc[zi]
        # 移除
        xc.remove(x_)
        yc.remove(y_)
        zc.remove(z_)
        # 把牌给下家
        yc.append(x_)
        zc.append(y_)
        xc.append(z_)
        # 排序
        xc = tuple(sorted(xc))
        yc = tuple(sorted(yc))
        zc = tuple(sorted(zc))
        res += h(xc, yc, zc, n-1)
    return fraction(res, total)


x = tuple(sorted(list(x)))
y = tuple(sorted(list(y)))
z = tuple(sorted(list(z)))
# print(x, y, z)
print(h(x, y, z, n))

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 468K, 提交时间: 2023-07-19 17:36:52

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const ll mod = 1e9+7;
ll sp[3][3];
ll now[3][3];
map<char,int>mp;
ll qpow(ll a,ll b)
{
    ll ret = 1;
    while(b)
    {
        if(b&1) ret = ret*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return ret;
}
ll dfs(int n)
{
    for(int i=0;i<3;++i)
        if(sp[i][0]*sp[i][1]*sp[i][2])
            return i==0;
    if(!n)return 0;
    ll ret = 0;
    int mx = 0;
    if(sp[0][1]>sp[0][mx]) mx = 1;
    if(sp[0][2]>sp[0][mx]) mx = 2;
    for(int i=0;i<3;++i)
    {
        if(!sp[1][i])continue;
        for(int j=0;j<3;++j)
        {
            if(!sp[2][j])continue;
            ll p = 1ll*sp[1][i]*sp[2][j]*qpow(9,mod-2)%mod;
            sp[0][mx]--;sp[1][mx]++;
            sp[1][i]--;sp[2][i]++;
            sp[2][j]--;sp[0][j]++;
            ret = (ret+dfs(n-1)*p%mod)%mod;
            sp[0][mx]++;sp[1][mx]--;
            sp[1][i]++;sp[2][i]--;
            sp[2][j]++;sp[0][j]--;
        }
    }
    return ret;
}
int main()
{
    mp['w'] = 0;mp['i'] = 1;mp['n'] = 2;
    int n;cin>>n;
    for(int i=0;i<3;++i)
        for(int j=0;j<3;++j)
        {
            char c;cin>>c;
            sp[i][mp[c]]++;
        }
    ll ans = dfs(n);
    cout<<ans<<endl;
}

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 536K, 提交时间: 2023-07-06 16:33:44

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r) for(int i = l;i <= r;i++)
#define frep(i,l,r) for(int i = r;i >= l;i--)
const int N = 2e3+10;
const ll p = 1e9+7;
int k[5][5];
string s1;
int to(char k1){
	if(k1 == 'w')return 1;
	if(k1 == 'i')return 2;
	return 3;
}
ll qpow(ll a,ll b){
	ll res = 1;
	while(b){
		if(b&1)res = res*a%p;
		a = a*a%p;
		b >>= 1;
	}
	return res;
}
ll dfs(int n){
	rep(i,1,3){
		if(k[i][1] == k[i][2]&&k[i][1] == k[i][3])return (i == 1);
	}
	if(!n)return 0;
	ll res = 0;
	rep(i,1,3){
		if(k[1][i] <= 1)continue;
		rep(j,1,3){
			rep(z,1,3){
				if(k[2][j] == 0||k[3][z] == 0)continue;
				ll p2 = k[2][j]*k[3][z]*qpow(9,p-2)%p;
				k[1][i]--,k[1][z]++;
				k[2][i]++,k[2][j]--;
				k[3][j]++,k[3][z]--;
				res += dfs(n-1)*p2%p;
				res %= p;
				k[1][i]++,k[1][z]--;
				k[2][i]--,k[2][j]++;
				k[3][j]--,k[3][z]++;
			}
		}
	}
	return res;
}

void solve(){
	int n;
	cin>>n;
	rep(j,1,3){
		cin>>s1;
		rep(i,0,s1.size()-1){
			k[j][to(s1[i])]++;
		}
	}
	cout<<(dfs(n))%p<<'\n';
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	solve();
    return 0;
}

Python3 解法, 执行用时: 54ms, 内存消耗: 4760K, 提交时间: 2023-07-16 10:37:12

n=eval(input())
A,B,C=list(input()),list(input()),list(input())
A.sort();B.sort();C.sort();
def judge(x):
    if sorted(x)==['i','n','w']:
        return True
    return False
mod=10**9+7;
mod27=pow(27,mod-2,mod)
mod18=pow(18,mod-2,mod)
def copyi(x):
    return [e for e in x]
def cal(A,B,C,tot):
    if judge(A):
        return 1
    elif judge(B) or judge(C):
        return 0
    elif tot==n:
        return 0
    ret=0
    if (A[0]==A[1] and A[1]==A[2]) or (A[0]!=A[1] and A[1]!=A[2] and A[0]!=A[2]):
        cp=list(range(3))
        modi=mod27
    else:
        modi=mod18
        if A[0]==A[1]:
            cp=range(2)
        elif A[0]==A[2]:
            cp=(0,2)
        else:
            cp=(1,2)
    for i in cp:
        for j in range(3):
            for k in range(3):
                Ai,Bi,Ci=copyi(A),copyi(B),copyi(C);
                Ai[i],Bi[j],Ci[k]=Ci[k],Ai[i],Bi[j]
                ret+=cal(Ai,Bi,Ci,tot+1)*modi
            
    return ret%mod
print(cal(A,B,C,0))

详情