A.矩阵 【牛客网_Wannafly模拟赛1】题目链接：https://www.nowcoder.com/acm/contest/submit/f8363c912a4c48a28b80f47e7102b6b8?ACMContestId=2&tagId=4
题目意思：这个题目是中文就不加解释了，首先这个子矩阵，就说明这个矩阵是实心的，并不是只是一个框，所以为什么我强调这点呢？因为比赛的时候我傻逼了，唉，心痛。
题目思路：二维哈希+二分
之前没学过哈希，所以第一次遇到就碰到二维的哈希qwq，首先哈希就是为了把一个字符串通过一个基数（一般是素数）把他压缩成一个值，冲突的概率极小，所以我们可以很方便的通过一个值来比较两个字符串是否相同，这是一维的哈希，如果是二维的哈希呢？没错我们需要两个基数，我们可以把一个字符串压成一个值，那么对于一系列由字符串压成的值再通过一个基数压成一个新的值，这样这个值就代表一个矩阵了。接下来再次附上我的灵魂画作

文章图片

如上图所示，[0,r]这个区间的字符串所压缩成的哈希值实际上是储存在下标为数组中r+1的格子里面。所以实际上每个下标为n的格子实际上储存了[0,n)这个左闭右开区间内部的哈希值，那么如果我们要的到某个区间的哈希值呢？我们来举一个例子，我们假设一个字符串是1234567，我们设基数为10（十进制方便理解），我们把这个情况画出来

文章图片

比如现在我们想要得到区间在字符串中区间为[3,5]的哈希值,或者说从3开始长度为(5-3+1)的区间的哈希值（如果是[3,6)就是（6-3）），就是123456-123000=456，也就是说如果是区间
[L,R)我们可以通过hash_get(L,R-L)来获取哈希值，如果是[L,R]，我们可以通过hash_get（L,R-L+1）来获得哈希值，想要得到哈希值我们需要预处理基数的次方表。
那么对于二维哈希表来说其实也一样，也是一样，这里就不做多余的说明。
然后就是二分，记住最大值最小化二分时终点是mid=(L+R+1)/2; 否则会死循环。
代码：

文章图片

文章图片

1 //Author: xiaowuga 2 #include 3 using namespace std; 4 #define inf 0x3f3f3f3f 5 #define MAX INT_MAX 6 #define mem(s,ch) memset(s,ch,sizeof(s)) 7 const long long N=518; 8 const long long mod=1e9+7; 9 typedef long long LL; 10 typedef int II; 11 typedef unsigned long long ull; 12 #define nc cout<<"nc"<a; 17 II n,m; 18 ull Hash[N][N]; 19 void init(){ 20x1[0]=1; x2[0]=1; 21for(II i=1; i<501; i++){ 22x1[i]=x1[i-1]*p1; 23x2[i]=x2[i-1]*p2; 24} 25 } 26 void hash_init(){ 27mem(Hash,0); 28for(II i=1; i<=n; i++){ 29for(II j=1; j<=m; j++){ 30Hash[i][j]=Hash[i][j-1]*p1+a[i-1][j-1]-'a'+1; 31} 32} 33for(II j=1; j<=m; j++){ 34for(II i=1; i<=n; i++){ 35Hash[i][j]=Hash[i-1][j]*p2+Hash[i][j]; 36} 37} 38 } 39 ull Hash_get(II x,II y,II l){ 40ull ans=Hash[x+l][y+l]-Hash[x][y+l]*x2[l]; 41ull res=Hash[x+l][y]-Hash[x][y]*x2[l]; 42return ans-res*x1[l]; 43 } 44 bool OK(II k){ 45if(!k) return false; 46unordered_setq; 47for(II i=0; i+k<=n; i++){ 48for(II j=0; j+k<=m; j++){ 49ull ans=Hash_get(i,j,k); 50if(q.find(ans)!=q.end()) return true; 51else q.insert(ans); 52} 53} 54return false; 55 } 56 int main() { 57ios::sync_with_stdio(false); cin.tie(0); 58init(); 59while(cin>>n>>m){ 60a.resize(n); 61for(II i=0; i>a[i]; 62hash_init(); 63II l=1,r=min(n,m)+1; 64while(l
View Code B.树 题目链接：https://www.nowcoder.com/acm/contest/submit/86fc8c46a8ce4c1fba763b8cf311f805?ACMContestId=2&tagId=4
题目意思：一颗树，现在有k种颜色，给n个节点染色，要求同样颜色的节点直接是可以互通的,问有多少种染色方法。
题目思路：很简单，如果同样颜色的节点可以互通，这个同样颜色的连通块必定是以这个区间内某个点为根的子树，我们可以发现一颗树每去掉一条边就是会多出一个连通块，那么发现我们去掉n-1条边中选择0条边形成一个连通块，k种颜色里面选择一种，也就是C（n-1,0）*A(k,1),，然后n-1条边里去掉一条边形成两个连通块，k中颜色里面选择两种那么就是
C（n-1,1）*A(k,2)，依次类推，后面的就不多做赘述，我们可以惊奇的发现貌似和树的形态没有任何关系，就是没有关系，真是太坑爹了。
代码：（处理大组合数和阶乘数的姿势就不做赘述了）

文章图片

文章图片

1 //Author: xiaowuga 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include