# 2019牛客国庆训练第一场

A. 全 1 子矩阵

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);

int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

int n, m;
char a[15][15];

int main()
{
while(~scanf("%d%d",&n, &m)){
int cnt = 0;
int x1 = 20;
int x2 = 0;
int y1= 20;
int y2 = 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++){
cin >> a[i][j];
if(a[i][j] == '1'){
cnt ++;
x1 = min(x1, i);
x2 = max(x2, i);
y1 = min(y1, j);
y2 = max(y2, j);
}
}
}
if(cnt == (x2 - x1 + 1) * (y2 - y1 + 1)){
puts("Yes");
}
else
puts("No");
}
return 0;
}



B. 组合数

C_{n}^{k}=\frac{n!}{k!\left( n-k \right) !}

=\frac{n\cdot(n-1)\cdot(n-2)\cdot\cdot\cdot(n-k+1)}{k\cdot(k-1)\cdot(k-2)\cdot\cdot\cdot1}

=\frac{n}{1}\cdot \frac{n-1}{k-1}\cdot \frac{n-2}{k-2}\cdot\cdot \frac{n-k+1}{k}

C_{n}^{k}=C_{n}^{n-k}

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e3 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);

int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

ll C(ll n, ll m){
if(n == 0 || n == m)  return 1ll;
if(n == 0 || n == m)  return 1ll;
if(m > n / 2) m = n - m;
__int128 ans = (__int128)1;
for(ll i = 1; i <= m; i ++){
ans = ans * (n - i + 1) / i;
if(ans > 1000000000000000000)
return 1000000000000000000ll;
}
return (ll)ans;
}

int main()
{
ll n, k;
while(~scanf("%d%d", &n, &k)){
printf("%lld\n", C(n, k));
}

return 0;
}



E. Numbers

DFS爆搜，当不能往下一层搜索时返回。

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e4 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);

int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

char s[100];
int ans = 0;
int len;
int vis[100];

void dfs(int u){
if(u >= len){
ans ++;
return ;
}
int ne;
for(int i = 1; i <= 2; i ++){
if(i == 1){
ne = s[u] - '0';
if(vis[ne] == 0){
vis[ne] ++;
dfs(u + 1);
vis[ne] --;
}
}
else if(s[u] != '0' && u + 1 < len){
ne = 10 * (s[u] - '0') + (s[u + 1] - '0');
if(vis[ne] == 0){
vis[ne] ++;
dfs(u + 2);
vis[ne] --;
}
}
}
}

int main()
{
while(~scanf("%s", s)){
ans = 0;
len = strlen(s);
memset(vis, 0, sizeof(vis));
dfs(0);
printf("%d\n", ans);
}
return 0;
}



F. 4 Buttons

\frac{n\cdot(n-1)}{2}\cdot (ab+bc+cd+da)+(a+b+c+d)\cdot n + 1

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 4e4 + 10;
const double eps = 1e-8;
const int inf = 1e9;
const double PI = acos(-1.0);
const int mod = 1e9 + 7;
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

ll n, a, b, c, d;

ll ksm(ll a, ll b, ll mod){
ll ans = 1ll % mod;
while(b){
if(b & 1) ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}

int main()
{
while(~scanf("%lld%lld%lld%lld%lld", &n, &a, &b, &c, &d)){
ll ans = 0;
ll t = n * (n - 1) % mod * ksm(2, mod - 2, mod) % mod;
ll k = ((((a * b) % mod + (b * c) % mod) % mod + (c * d) % mod) % mod + (d * a) % mod) % mod;

ans = (1ll + (a + b + c + d) % mod * n % mod) + ((t * k) % mod) % mod;
printf("%lld\n", ans % mod);
}
return 0;
}



C. Distinct Substrings

\frac{(n+1)\cdot(n+2)}{2}-\sum{h1} - \frac{n\cdot(n+1)}{2} + \sum{h0}

(n+1)-(\sum{h1 - \sum{h0}})

3和31213
13和131213
213和2131213
1213和12131213

p[s[i]] = max(p[s[i]], z[i + 1] + 1)

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const double eps = 1e-8;
const int inf = 1e9;
const int maxn = 1e6 + 10;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

int n, m;
vector<int> s;

int Next[maxn];
int extend[maxn];   // extend[i] 表示 子串 T与 母串 S[i, n-1]的最长公共前缀
//预处理next 数组
void getNext(vector<int> str){
int i = 0, j, po, len = n;
Next[0] = len;
while(i + 1 < len && str[i] == str[i + 1])   // 计算 next[1]
++i;
Next[1] = i;
po = 1; //初始化 po位置
for(int i = 2; i < len; ++i){
if(Next[i - po] + i < Next[po] + po){
Next[i] = Next[i - po];
}else{  //第二种情况，要继续匹配才能得到next[i]的值
j = Next[po] + po - i;
if(j < 0)
j = 0;  //如果i>po+next[po],则要从头开始匹配
while(i + j < len && str[j] == str[j + i])
++j;
Next[i] = j;
po = i;
}
}
}
//计算extend 数组，是求s1的extend,
//extend[i]代表的是s1[i]~s[n-1],与s2数组前缀的最大相同是多少。
void exkmp(vector<int> s1, vector<int> s2){// s2 是子串，s1是母串
int i = 0, j, po, len = n, l2 = n;
getNext(s2);
while(i < l2 && i < len && s1[i] == s2[i])
++i;
extend[0] = i;
po = 0; //初始化po的位置
for(i = 1; i < len; ++i){
if(Next[i - po] + i < extend[po] + po){
extend[i] = Next[i - po];
}else{
j = extend[po] + po - i;
if(j < 0)
j = 0;
while(i + j < len && j < l2 && s1[j + i] == s2[j]){
++j;
}
extend[i] = j;
po = i;
}
}
}

void solve(){
for(int i = 0; i <= n; i ++){
Next[i] = 0;
extend[i] = 0;
}
reverse(s.begin(), s.end());
exkmp(s, s);
extend[0] = 1;
vector<int> p(m + 1);
for(int i = 0; i < n; i ++){
p[s[i]] = max(p[s[i]], 1 + extend[i + 1]);
}

ll ans = 0, k = 3;
for(int i = 1; i <= m; i ++){
ans ^= k * (n + 1 - p[i]) % mod;
(k *= 3) %= mod;
}
printf("%lld\n", ans);
}

int main()
{
while(~scanf("%d%d", &n,&m)){
s.resize(n);
for(int i = 0; i < n; i ++){
scanf("%d", &s[i]);
}
solve();
}
return 0;
}



Z算法：

#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const double eps = 1e-8;
const int inf = 1e9;
const int maxn = 1e6 + 10;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
int dir[4][2] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};

int n, m;
vector<int> s;
int z[maxn];

void get_z()
{
int l=0,r=0;
for (int i=1;i<n;i++)
{
if (i>r)
{
l=i,r=i;
while (r<n && s[r-l]==s[r]) r++;
z[i]=r-l,r--;
}
else
{
int k=i-l;
if (z[k]<r-i+1) z[i]=z[k];
else
{
l=i;
while (r<n && s[r-l]==s[r]) r++;
z[i]=r-l,r--;
}
}
}
}

void solve(){
for(int i = 0; i <= n; i ++){
z[i] = 0;
}
reverse(s.begin(), s.end());
get_z();
vector<int> p(m + 1);
for(int i = 0; i < n; i ++){
p[s[i]] = max(p[s[i]], 1 + z[i + 1]);
}

ll ans = 0, k = 3;
for(int i = 1; i <= m; i ++){
ans ^= k * (n + 1 - p[i]) % mod;
k = (k * 3) % mod;
}
printf("%lld\n", ans);
}

int main()
{
while(~scanf("%d%d", &n,&m)){
s.resize(n);
for(int i = 0; i < n; i ++){
scanf("%d", &s[i]);
}
solve();
}
return 0;
}