惠州网站制作维护,wordpress侧边栏颜色,wordpress增加主题配置,wordpress add pageA.牛妹的游戏
Ramsey定理#xff1a;人话解释任意六个人中要么至少三个人认识#xff0c;要么至少三个不认识。 结论简要证明: 假设 666 个据点分别为 A,B,C,D,E,FA,B,C,D,E,FA,B,C,D,E,F那么在 A 连向其它据点的控制链中#xff0c;必然至少有 333条链被同一方控制#x…A.牛妹的游戏
Ramsey定理人话解释任意六个人中要么至少三个人认识要么至少三个不认识。 结论简要证明: 假设 666 个据点分别为 A,B,C,D,E,FA,B,C,D,E,FA,B,C,D,E,F那么在 A 连向其它据点的控制链中必然至少有 333条链被同一方控制不妨假设它们为 AB,AC,ADAB,AC,ADAB,AC,AD。如此一来只要 BC,BD,CDBC,BD,CDBC,BD,CD 中有任意一条链也被这一方控制则可以形成控制区域如果这三条链都没有被这一方控制也就意味着它们都被对方控制了则它们同样可以形成控制区域。 #define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef pairint,int pii;
typedef long long ll;
const int N500010;
int n,m;
int e[10][10];
int main()
{IO;int T1;cinT;while(T--){cinnm;memset(e,0,sizeof e);if(n5){for(int i1;im;i){int a,b;cinab;}coutyes\n;continue;}for(int i1;im;i){int a,b;cinab;e[a][b]e[b][a]1;}bool ok0;for(int i1;in;i)for(int ji1;jn;j)for(int kj1;kn;k)if(e[i][j]e[j][k]e[k][i]||!e[i][j]!e[j][k]!e[k][i])ok1;if(ok) coutyes\n;else coutno\n;}return 0;
}B.病毒扩散
打表找规律杨辉三角。 第四秒后扩张现象如下图
[1×14×16×14×11×14×16×24×31×46×14×31×64×11×41×1]\begin{bmatrix} 1×14×16×14×11×1\\4×16×24×31×4\\6×14×31×6\\4×11×4\\1×1 \end{bmatrix}⎣⎢⎢⎢⎢⎡1×14×16×14×11×14×16×24×31×46×14×31×64×11×41×1⎦⎥⎥⎥⎥⎤ 好像不是那么明显我们把乘号左边和右边的数分别拿出来 左边:[146414641641411]左边:\begin{bmatrix} 14641\\4641\\641\\41\\1 \end{bmatrix}左边:⎣⎢⎢⎢⎢⎡146414641641411⎦⎥⎥⎥⎥⎤
右边:[111111234136141]右边:\begin{bmatrix} 11111\\1234\\136\\14\\1 \end{bmatrix}右边:⎣⎢⎢⎢⎢⎡111111234136141⎦⎥⎥⎥⎥⎤ 不难发现这两个矩阵的这些数和组合数杨辉三角有关 考虑位置为(x,y)(x,y)(x,y)时间是ttt的情况下 左边的数CtxyC_{t}^{xy}Ctxy右边的数CxyxC_{xy}^xCxyx那么最终答案就是Ctxy×CxyxC_{t}^{xy}×C_{xy}^xCtxy×Cxyx 预处理阶乘和逆元即可O(1)O(1)O(1)得到每个位置的答案 我看不懂的官方证明转化
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
typedef pairint,int pii;
typedef long long ll;
const int N5010;
const ll mod998244353;
ll fact[N],infact[N];
ll qmi(ll a,ll b,ll p)
{ll res1;while(b){if(b1) resres*a%p;b1;aa*a%p;}return res;
}
void init()
{fact[0]infact[0]1;for(int i1;iN;i){fact[i]fact[i-1]*i%mod;infact[i]qmi(fact[i],mod-2,mod);}
}
int n;
int main()
{IO;int T1;//cinT;init();while(T--){cinn;while(n--){int x,y,t;cinxyt;if(xyt) cout0\n;else{ll res1;resres*fact[t]*infact[xy]%mod*infact[t-x-y]%mod;resres*fact[xy]%mod*infact[x]%mod*infact[y]%mod;coutres\n;}}}return 0;
}
C.牛牛染颜色
树形dp 状态表示f(i,0/1)f_{(i,0/1)}f(i,0/1)表示选择/不选择uuu 这个节点后以 uuu 为根的子树的合法方案数。 状态转移 若选择 uuu 这个节点则子树内可以随便选点每个子树独立乘法原理可得转移f(i,1)∏j∈sonf(j,0)f(j,1)f_{(i,1)}\prod_{j\in son} f_{(j,0)}f_{(j,1)}f(i,1)∏j∈sonf(j,0)f(j,1) 若不选择uuu 这个节点则最多选择某一个子树由加法原理可得转移f(i,0)1∑j∈son(f(j,0)f(j,1)−1)f_{(i,0)}1\sum_{j\in son}(f_{(j,0)}f_{(j,1)}-1)f(i,0)1∑j∈son(f(j,0)f(j,1)−1) f(i,0)f_{(i,0)}f(i,0)包含空集的方案所以在枚举子树统计的时候每颗子树贡献的答案要减 111但最后也要把空集的情况算上还要加个111
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
const int N1000010,mod1e97;
int h[N],e[2*N],ne[2*N],idx;
ll f[N][2];
int n;
void add(int a,int b)
{e[idx]b;ne[idx]h[a];h[a]idx;
}
void dfs(int u,int fa)
{f[u][0]f[u][1]1;for(int ih[u];i!-1;ine[i]){int je[i];if(jfa) continue;dfs(j,u);f[u][1](f[u][1]*(f[j][0]f[j][1]))%mod;f[u][0](f[u][0]f[j][1]f[j][0]-1)%mod;}
}
int main()
{IO;int T1;//cinT;while(T--){cinn;memset(h,-1,sizeof h);for(int i1;in;i){int a,b;cinab;add(a,b),add(b,a);}dfs(1,-1);cout(f[1][0]f[1][1])%mod\n;}return 0;
}D. 牛牛的呱数
对于大数基本上都是取模达到我们想要的目的。 由此可以把原串取模后的答案记录下来并且记录它的长度边权和别的串相接的过程就类似从一个状态到另一个状态只需要预处理10k%p10^k\%p10k%p的结果跑最短路即可。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includequeue
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef pairint,int pii;
const int N210;
int ten[1000010];
struct node
{int val,len;
}a[N];
int dist[N],n,p;
bool st[N];
void dijkstra()
{memset(dist,0x3f,sizeof dist);priority_queuepii,vectorpii,greaterpii q;for(int i1;in;i) {dist[a[i].val]min(dist[a[i].val],a[i].len);q.push({a[i].len,a[i].val});}while(q.size()){int tq.top().second;q.pop();if(st[t]) continue;st[t]1;for(int i1;in;i){int now(t*ten[a[i].len]%pa[i].val)%p;if(dist[now]dist[t]a[i].len){dist[now]dist[t]a[i].len;q.push({dist[now],now});}}}
}
int main()
{IO;int T1;//cinT;while(T--){cinnp;ten[0]1;for(int i1;i1000000;i) ten[i]ten[i-1]*10%p;for(int i1;in;i){string s;cins;a[i].lens.size();reverse(s.begin(),s.end());ll base1;ll now0;for(auto t:s){now(nowbase*(t-0)%p)%p;basebase*10%p;}a[i].valnow%p;}dijkstra();if(dist[0]0x3f3f3f3f) cout-1\n;else coutdist[0]\n;}return 0;
}要加油哦~~
