9.29总结

这星期学了概率和组合数学

这是我觉得的一个有趣的题目，每个人身上都有n-1根绳子，如果组不成稳定三角，那么肯定有两个人相邻两根绳子颜色不一样，那么每两个这样的人就会贡献一个不稳定三角形，所以只要所有三角形减去每个人红绳乘黑绳的数量的和除二就是答案

这个也蛮有意思的，求出所有路径的长度和/所有路径的条数即是答案

通过代码：

#include<bits/stdc++.h>
#include <iomanip>
#define ll long long
#define max_int 2147483647
#define max_ll 9223372036854775807
using namespace std;
int M=998244353;
ll ksm(ll a, ll b){ll res = 1;while(b) {if(b & 1) //判断b的二进制在此位是否为1res = res * a % M;a = a * a % M; //下一位的a的值b >>= 1;}return res;
}
ll mod(ll a,ll b){return a * ksm(b, M - 2) % M;
}
vector<int>graph[100005];
int main() {ll n,m,sum=0;cin>>n>>m;vector<int>longth(n+1);vector<int>fananshu(n+1,1);vector<int>in(n+1);for(int i=0,u,v;i<m;++i){cin>>u>>v;graph[u].push_back(v);in[v]++;}queue<int>q;for(int i=1;i<=n;++i) if(!in[i]){q.push(i);}while(!q.empty()){int u=q.front();q.pop();for(int v:graph[u]){longth[v]+=(longth[u]+fananshu[u])%M;longth[v]%=M;fananshu[v]+=fananshu[u]%M;fananshu[v]%=M;in[v]--;if(!in[v])q.push(v);}}ll f=0,l=0;for(int i=1;i<=n;++i){f+=fananshu[i];f%=M;l+=longth[i];l%=M;//cout<<fananshu[i]<<' '<<longth[i]<<endl;}//cout<<l<<' '<<f<<endl;cout<<mod(l,f)<<endl;return 0;
}