获胜的概率2

 

问题描述 有n(2≤n≤10)个玩家玩游戏，他们按1到n编号。第i(1≤i≤n)个玩家有ti个喜欢的玩家，给出第i个玩家喜欢的玩家的编号列表。 最初1号玩家拿着一朵花，游戏进行k(0≤k≤1018)个回合，每个回合拿着花的人会把花等概率地送给自己喜欢的人之一，k回合游戏后拿着花的人获胜。分别求n个人获胜的概率，对10⁹+7取模。 输入格式 第一行，包括两个正整数n,k,分别表示玩家人数和游戏轮数。 以下n行，每行首先有一个非负整数ti(1≤ti≤n),表示第i个玩家有ti个喜欢的人。然后输入ti个互不相同的正整数，表示第i个玩家喜欢的人的编号。 输出格式 共n行，每行一个正整数pi(1≤i≤n)表示k次游戏后第i个人拿着花的概率，对10⁹+7取模。 令M=10⁹+7,可以证明所求概率可以写成既约分数号的形式，其中P,q均为整数且q≠0(modM)。应输出整数p×q-¹(mod M)。 样例输入 41 224 12 224 11 样例输出 0 500060004 0 500000004 说明 1轮游戏后，花在第1个人和第3个人手中的概率为0,在第2个人和第4个人手中的概率是。 评测数据规模 2≤n≤10,0≤k≤10l⁸。 运行限制 语言 最大运行时间 最大运行内存 C++ 1s 256M C 1s 256M Java 2s 256M Python3 3s 256M

官方答案：

 

 

 

C++代码： 

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
using LL=long long;
const int mod=1e9+7;
int n;
LL k;
struct asdf{
    int n,m;
    LL a[11][11];
    asdf(int x=10,int y=10,int t=0)
    {
        n=x;
        m=y;
        memset(a,0,sizeof(a));
        if (t) 
            for (int i=0;i<min(m,n);++i) a[i][i]=1;
    }
    asdf operator * (asdf b)
    {
        asdf ans;
        memset(ans.a,0,sizeof(ans.a));
        unsigned long long ul=0;
        for (int i=0;i<n;++i)
            for (int k=0;k<m;++k)
                for (int j=0;j<b.m;++j)
                    ans.a[i][j]=(ans.a[i][j]+a[i][k]*b.a[k][j]%mod)%mod;
        return ans;
    }
};
LL poww(LL a,LL b)
{
    LL ans=1;
    for (;b;b>>=1,a=a*a%mod)
        if (b&1) ans=ans*a%mod;
    return ans;
}
asdf poww(asdf a,LL b)
{
    asdf ans(a.n,a.n,1);
    for (;b;b>>=1,a=a*a)
        if (b&1) ans=ans*a;
    return ans;
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>k;
    asdf p(n,1,1),X;
    LL q;
    for (int i=1,k,x;i<=n;++i)
    {
        cin>>k;
        q=poww(k,mod-2);
        for (int j=1;j<=k;++j)
        {
            cin>>x;
            X.a[x-1][i-1]=q;
        }
    }
    p=poww(X,k)*p;
    for (int i=0;i<n;++i) cout<<p.a[i][0]<<"\n";
    return 0;
}