A 牛妹的游戏

链接：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

UPD:数据保证不会有两条控制链控制的据点完全相同，也保证不会有某条控制链两端控制的据点相同。

牛妹最近沉迷于一个名为 ingress 的游戏中...

游戏中，蓝绿营两个对立阵营互相角力，通过争夺据点来控制区域。具体来说，二维的平面上分布有若干据点，玩家可以通过XM扫描器来控制这些据点。
同一阵营控制的两个据点可以相连成为一条被该阵营控制的链。而同一阵营控制的三条链，首尾相接可以形成一块被该阵营控制的区域。
如下图为一块被蓝方控制的区域：

在这里插入图片描述

但是这样的游戏没有一个胜利或失败结局，牛牛觉得很不舒服，于是他开发出了 imgress。这个游戏和 ingress
的区别在于，如果一个阵营控制了一块区域，则形成这块区域的据点无法再被另一阵营控制。此外，imgress
的玩家并非直接对据点进行控制，而是通过在据点间形成控制链来间接控制对应据点，于是可能出现同一个据点被两方的控制链所使用的情况。

现在，牛妹加入了蓝方阵营，她已经得知了场上的总据点数，和蓝方已经形成的所有控制链。
现在她想知道目前场上是否可能已经存在被玩家控制的区域，你需要帮她解决这个问题。

输入描述:

第一行一个正整数 T，表示数据组数。每组数据的第一行有两个正整数 n 和 m，表示场上总据点数为 n，此时蓝方已经形成了 m 条控制链。
接下来 m 行，每行有两个正整数 x 和 y，表示这条控制链由据点 x 和据点 y 形成。

输出描述:

对于每组数据，如果目前场上有可能存在被玩家控制的区域，则输出一行 "yes"，否则输出一行 "no"。（均不包含引号）

示例1
输入

输出

yes
no

说明

对于第一组数据，蓝方在所有据点间形成了控制链，此时的情况如下图所示：

可以发现蓝方已经形成了控制区域。

对于第二组数据，蓝方的 5 条控制链首尾相接，如下图所示：

在这里插入图片描述

此时蓝方没有形成控制区域，同时，可以发现绿方即使控制了所有蓝方没有控制的链，也无法形成控制区域。

题意：

我来把题目浓缩下：就是给你一个无向图，问这个图和它的补图是否存在三元环？
如果图本身有三元环就是蓝方赢，如补图有三元环，就是绿方赢，但题目是问你蓝绿方有一方能赢就输出yes，都不能就输出no

题解：

有一个结论：如果点>=6的话，它以及它的补图一定存在三元环。
网上说这个叫拉姆塞结论（~~我们离散也没讲过~~ ）
点数小于6的话，暴力就OK了，先标记给的边，三层for循环，看看任意三个边能不能构成环。

代码：

#include<bits/stdc++.h>
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int mod = 1e9 + 7;
const int maxn=102;
int n,sum;
int f[102][102];
void biaoji(int x,int y)
{
    f[x][y]=1;
    f[y][x]=1;
}
int main()
{
    int T,n,m,a,b;
    cin>>T;
    while(T--)
    {
        sum=0;
        mem(f);
        cin>>n>>m;
        for(int i=1;i<=m;i++)
        {
            cin>>a>>b;
            biaoji(a,b);
        }
        if(n>=6)
        {
        cout<<"yes";    
        }
        else
        {
            for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            for(int k=j+1;k<=n;k++)
            {
                int w=f[i][j]+f[j][k]+f[k][i];
                if(w==0||w==3)sum++;
                if(sum)break;
            }
        if(sum)cout<<"yes"<<endl;
        else cout<<"no"<<endl;
        }

    } 
}

B 病毒扩散

链接：

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述
在这里插入图片描述
牛牛想知道，对于特殊的 \ n n 个点，在时刻\ t t 感染者的数量。
输入描述:

输出描述:
对于每一个特殊的点，输出一行一个非负整数，表示在 \ t t 时刻这个点的感染者数量，对 998244353 取模。
示例1
输入
复制
3
0 0 1
1 1 2
2 0 2
输出
复制
1
2
1
说明
见题目描述中的图片。
示例2
输入
复制
5
5 5 7
2 7 9
0 14 14
0 14 15
14 29 100
输出
复制
0
36
1
15
891148910
备注:
在这里插入图片描述
题解：
我们可以转化下题意：

从（0,0）出发，每次可以走一步，或者原地不动，问t时刻走到（x，y）的方案数量

想想这个怎么做？不会
因为一次最多走一步，所以到（x，y）至少要走x+y个时刻，
我们设sum=x+y，sum一定要大于t否则怎么能走到，要在t时刻内走到，就是在t内选sum个时刻，共有C^t^~~sum~~
在移动的sum个步数里，有x步需要x坐标加一，其余要将y坐标加一，一共有C^x^~~sum~~
综上，乘在一起就可以

还一个想法：一共t时刻，其中选出x个用于x坐标加一，剩下t-x中选出y个用于y坐标加一，剩下的原地不动
这样就是C^x^t*C^y^~~t-x~~
求组合数时，
乘法逆元：（a/b）% mod = a * b^(mod-2)，mod为素数
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 998244353;
ll poww(ll a, ll b)
{
    ll ans = 1;
    a = a % mod;
    while (b)
    {
        if(b & 1) ans = (ans* a) % mod;
        a = ( a*a )% mod;
        b = b >> 1;
    }
    return ans;
}

ll c[maxn];
int main()
{
     int n;
     ll c1,c2;
    c[1]=1,c[0]=1;
    for( ll i=2;i<maxn;i++ ) c[i]=(c[i-1]*i)%mod;

    scanf("%d",&n);
    while( n-- )
    {
        int a,b,t;
        scanf("%d%d%d",&a,&b,&t);
        if( a+b>t )
        {
            cout<<"0"<<endl;
            continue;
        }
         c1=( c[t] * poww( c[t-b] * c[b], mod - 2) ) % mod;
         c2=( c[t-b] * poww( c[t-b-a] * c[a], mod - 2) ) % mod;
        printf("%lld\n",(c1*c2)%mod);
    }
    return 0;
}

我看还有一个是找规律，用杨辉三角形做的，tql

牛妹的游戏&&病毒扩散

A 牛妹的游戏

题目描述

题意：

题解：

代码：

B 病毒扩散