1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int N=3030; 6 ll a[N],pre[N],ans[N],inv3; 7 const ll mod=998244353; 8 9 ll quick(ll a,ll b) { 10 ll res = 1; 11 while (b) { 12 if (b & 1) { 13 res = res * a % mod; 14 } 15 a = a * a % mod; 16 b = b >> 1; 17 } 18 return res; 19 } 20 21 ll inv(int x){ 22 return quick(x,mod-2); 23 } 24 25 void init() { 26 for (int i = 1; i <= 3000; i++) { 27 a[i] = i * (i - 1); 28 } 29 for (int i = 1; i <= 3000; i++) { 30 pre[i] = (pre[i - 1] + a[i]) % mod; 31 } 32 33 for (int i = 1; i <= 3000; i++) { 34 ans[i] = (pre[i] * inv3%mod *inv(i)) % mod; 35 } 36 } 37 int main() { 38 inv3 = inv(3); 39 init(); 40 int n; 41 while (~scanf("%d", &n)) { 42 printf("%lld ", ans[n]); 43 } 44 }
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const ll mod=1e6+3; 6 ll ans[mod+1],n; 7 int main(){ 8 ans[0]=1; 9 for (int i=1;i<=mod;i++){ 10 ans[i]=ans[i-1]*i%mod; 11 } 12 while (~scanf("%lld",&n)){ 13 if (n>=mod){ 14 printf("0 "); 15 }else{ 16 printf("%lld ",ans[n]); 17 } 18 } 19 }
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int maxn=4e5+5; 6 int a[maxn],n,rt[maxn],q; 7 vector<int>vec; 8 struct pstree{ 9 struct pst{ 10 int lch,rch,val; 11 }z[maxn*20]; 12 int cnt; 13 inline void insert(int &p,int pre,int l,int r,int q) { 14 p = ++cnt; 15 z[p] = z[pre]; 16 ++z[p].val; 17 if (l == r) { 18 return; 19 } 20 int mid = (l + r) >> 1; 21 if (q <= mid) { 22 insert(z[p].lch, z[pre].lch, l, mid, q); 23 } else { 24 insert(z[p].rch, z[pre].rch, mid + 1, r, q); 25 } 26 } 27 28 inline int query(int l1,int r1,int l,int r,int q) { 29 if (l == r) { 30 return l; 31 } 32 int mid = (l + r) >> 1; 33 int tmp = z[z[r1].lch].val - z[z[l1].lch].val; 34 if (tmp >= q) { 35 return query(z[l1].lch, z[r1].lch, l, mid, q); 36 } else { 37 return query(z[l1].rch, z[r1].rch, mid + 1, r, q - tmp); 38 } 39 } 40 }pstree; 41 int main() { 42 while (~scanf("%d%d", &n, &q)) { 43 for (int i = 1; i <= n; i++) { 44 scanf("%d", &a[i]); 45 vec.push_back(a[i]); 46 } 47 sort(vec.begin(), vec.end()); 48 vec.erase(unique(vec.begin(), vec.end()), vec.end()); 49 for (int i = 1; i <= n; i++) { 50 a[i] = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin() + 1; 51 pstree.insert(rt[i], rt[i - 1], 1, n, a[i]); 52 } 53 while (q--) { 54 int l,r; 55 scanf("%d%d", &l, &r); 56 int cnt = r - l + 1; 57 int f = 0; 58 if (cnt < 3) { 59 puts("-1"); 60 continue; 61 } 62 int tmp = min(60, cnt); 63 int maxx[3]; 64 for (int i = 0; i < 3; i++) { 65 maxx[i] = vec[pstree.query(rt[l - 1], rt[r], 1, n, cnt - i) - 1]; 66 } 67 if (maxx[0] - maxx[1] < maxx[2]) { 68 printf("%lld ", (ll) maxx[0] + maxx[1] + maxx[2]); 69 continue; 70 } 71 for (int i = 3; i < tmp; i++) { 72 maxx[0] = maxx[1]; 73 maxx[1] = maxx[2]; 74 maxx[2] = vec[pstree.query(rt[l - 1], rt[r], 1, n, cnt - i) - 1]; 75 if (maxx[0] - maxx[1] < maxx[2]) { 76 f = 1; 77 printf("%lld ", (ll) maxx[0] + maxx[1] + maxx[2]); 78 break; 79 } 80 } 81 if (!f) { 82 puts("-1"); 83 } 84 } 85 vec.clear(); 86 pstree.cnt = 0; 87 } 88 }
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 const int maxn=100010; 5 struct node{ 6 int lz,mx; 7 }t[maxn*4]; 8 vector<int>pos[maxn]; 9 10 int a[maxn],now[maxn],tmp,n,c,k; 11 12 void build(int rt,int l,int r) { 13 t[rt].mx = 0; 14 t[rt].lz = 0; 15 if (l == r) { 16 return; 17 } 18 int mid = (l + r) >> 1; 19 build(rt << 1, l, mid); 20 build(rt << 1 | 1, mid + 1, r); 21 } 22 23 void pushdown(int rt) { 24 if (t[rt].lz == 0) { 25 return; 26 } 27 t[rt << 1].mx += t[rt].lz; 28 t[rt << 1 | 1].mx += t[rt].lz; 29 t[rt << 1].lz += t[rt].lz; 30 t[rt << 1 | 1].lz += t[rt].lz; 31 t[rt].lz = 0; 32 } 33 34 void update(int rt,int l,int r,int k,int L,int R) { 35 if (l <= L && R <= r) { 36 t[rt].lz += k; 37 t[rt].mx += k; 38 return; 39 } 40 pushdown(rt); 41 int mid = (L + R) >> 1; 42 if (l <= mid) { 43 update(rt << 1, l, r, k, L, mid); 44 } 45 if (r > mid) { 46 update(rt << 1 | 1, l, r, k, mid + 1, R); 47 } 48 t[rt].mx = max(t[rt << 1].mx, t[rt << 1 | 1].mx); 49 } 50 51 int query(int rt,int l,int r) { 52 if (l == r) 53 return l; 54 int ans = -1, mid = (l + r) >> 1; 55 pushdown(rt); 56 if (t[rt << 1].mx == c) { 57 ans = query(rt << 1, l, mid); 58 } else if (t[rt << 1 | 1].mx == c) { 59 ans = query(rt << 1 | 1, mid + 1, r); 60 } 61 return ans; 62 } 63 64 int main() { 65 while (~scanf("%d%d%d", &n, &c, &k)) { 66 for (int i = 1; i <= c; i++) { 67 pos[i].clear(); 68 pos[i].push_back(0); 69 } 70 71 for (int i = 1; i <= n; i++) { 72 scanf("%d", &a[i]); 73 pos[a[i]].push_back(i); 74 } 75 if (k == 1) { 76 printf("%d ", n); 77 continue; 78 } 79 build(1, 1, n); 80 int ans = 0; 81 memset(now, 0, sizeof(now)); 82 for (int i = 1; i <= n; i++) { 83 84 int t = a[i], p = ++now[t]; 85 update(1, i, i, c - 1, 1, n); 86 if (pos[t][p - 1] + 1 <= pos[t][p] - 1) { 87 update(1, pos[t][p - 1]+1, pos[t][p] - 1, -1, 1, n); 88 } 89 90 if (p >= k) { 91 update(1, pos[t][p - k] + 1, pos[t][p - k + 1], 1, 1, n); 92 } 93 tmp = query(1, 1, n); 94 if (tmp != -1) { 95 ans = max(ans, i - tmp + 1); 96 } 97 } 98 printf("%d ", ans); 99 } 100 }
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn=300005;
int ans[maxn];
ull ha[maxn],pp[maxn];
const ull hash1 = 201326611;
ull getha(int l,int r) {
if (l == 0) return ha[r];
return ha[r] - ha[l - 1] * pp[r - l + 1];
}
bool check(int l,int r) {
int len = r - l + 1;
int mid = (r + l) >> 1;
if (len & 1)
return getha(l, mid) == getha(mid, r);
else return getha(l, mid) == getha(mid + 1, r);
}
struct PAM {//回文树
int next[maxn][26], fail[maxn], len[maxn], cnt[maxn], S[maxn];
int index[maxn];
// 一个结点一个本质不同的回文串
//len[i] 表示回文串i的长度
// next[i][c]编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号（儿子）。
//cnt[i] 节点i表示的本质不同的串的个数
//（建树时求出的不是完全的，最后重新统计一遍以后才是正确的）。
// fail[i] 节点i失配以后跳转不等于自身的节点i表示的回文串的最长后缀回文串
//last 新添加一个字母后所形成的最长回文串表示的节点
// S[i] 第i次添加的字符（一开始设S[0] = -1，也可以是任意一个在串S中不会出现的字符）
//2~id-1 添加的结点 n 添加的字符个数
//index[i] 是i号结点是插入到第 index[i] 号字符串产生的结点
//若字符从0开始，index[i]对应 区间[ index[i]-len[i],index[i]-1 ]
int id;//节点指针
int n;//字符数组指针
int last;
int newnode(int x) {
for (int i = 0; i < 26; i++)
next[id][i] = 0;
cnt[id] = 0;
len[id] = x;
return id++;
};
void init() {
id = 0;
newnode(0);
newnode(-1);
//两个根节点
fail[0] = 1;
S[0] = -1;//开头放一个字符集中没有的字符，减少特判
last = n = 0;
}
int getfail(int x) { //和KMP一样，失配后找一个尽量最长的
while (S[n - len[x] - 1] != S[n]) x = fail[x];
return x;
}
int Insert(int c) {
c -= 'a';
S[++n] = c;
int cur = getfail(last);//通过上一个回文串找这个回文串的匹配位置
if (!next[cur][c]) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
int now = newnode(len[cur] + 2);//新建节点
fail[now] = next[getfail(fail[cur])][c];//和AC自动机一样建立fail指针，以便失配后跳转
next[cur][c] = now;
}
last = next[cur][c];
cnt[last]++;
index[last] = n;//当前回文子串结尾的地方+1
}
void getsum() {
for (int i = id - 1; i >= 0; i--)
cnt[fail[i]] += cnt[i];
//父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
//从2开始，因为0和1为根节点
for (int i = 2; i < id; i++) {
//id[i]为结尾+1，len为长度,所以起点为id[i]-len[i]，终点为id[i]-1
//这样就可以保存所有回文子串的位置和长度的信息了
if (check(index[i] - len[i], index[i] - 1)) {
ans[len[i]] += cnt[i];
}
}
}
}pam;
char s[maxn];
int main() {
pp[0] = 1;
for (int i = 1; i < maxn; i++)
pp[i] = pp[i - 1] * hash1;
while (~scanf("%s", s)) {
int len = strlen(s);
for (int i = 0; i <= len; i++)
ans[i] = 0;
pam.init();
for (int i = 0; i < len; i++)
pam.Insert(s[i]);
ha[0] = s[0];
for (int i = 1; i < len; i++)
ha[i] = ha[i - 1] * hash1 + s[i];
pam.getsum();
for (int i = 1; i <= len; i++) {
printf("%d", ans[i]);
if (len == i)
printf("
");
else printf(" ");
}
}
}
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const ll maxn=505; 5 const ll maxm=5e5+7; 6 const ll inf=0x3f3f3f3f3f3f3f3f; 7 struct Dinic { 8 struct Edge { 9 ll next, f, to; 10 } e[maxm]; 11 ll head[maxn], dep[maxn], tol, ans; 12 int cur[maxn]; 13 int src, sink, n; 14 15 void add(int u, int v, ll f) { 16 tol++; 17 e[tol].to = v; 18 e[tol].next = head[u]; 19 e[tol].f = f; 20 head[u] = tol; 21 tol++; 22 e[tol].to = u; 23 e[tol].next = head[v]; 24 e[tol].f = 0; 25 head[v] = tol; 26 } 27 28 bool bfs() { 29 queue<int> q; 30 memset(dep, -1, sizeof(dep)); 31 q.push(src); 32 dep[src] = 0; 33 while (!q.empty()) { 34 int now = q.front(); 35 q.pop(); 36 for (int i = head[now]; i; i = e[i].next) { 37 if (dep[e[i].to] == -1 && e[i].f) { 38 dep[e[i].to] = dep[now] + 1; 39 if (e[i].to == sink) 40 return true; 41 q.push(e[i].to); 42 } 43 } 44 } 45 return false; 46 } 47 48 int dfs(int x, ll maxx) { 49 if (x == sink) 50 return maxx; 51 for (int &i = cur[x]; i; i = e[i].next) { 52 if (dep[e[i].to] == dep[x] + 1 && e[i].f > 0) { 53 ll flow = dfs(e[i].to, min(maxx, e[i].f)); 54 if (flow) { 55 e[i].f -= flow; 56 e[i ^ 1].f += flow; 57 return flow; 58 } 59 } 60 } 61 return 0; 62 } 63 64 ll dinic(int s, int t) { 65 ans = 0; 66 this->src = s; 67 this->sink = t; 68 while (bfs()) { 69 for (int i = 0; i <= n; i++) 70 cur[i] = head[i]; 71 while (int d = dfs(src, inf)) 72 ans += d; 73 } 74 return ans; 75 } 76 77 void init(int n) { 78 this->n = n; 79 memset(head, 0, sizeof(head)); 80 tol = 1; 81 } 82 } G; 83 84 int main() { 85 ll n,m,sum,t,s,u,v,a,b,c,A,C,E,ans; 86 while (~scanf("%lld%lld", &n, &m)) { 87 G.init(n); 88 sum = 0; 89 t = n + 1; 90 s = 0; 91 for (int i = 1; i <= m; i++) { 92 scanf("%lld%lld%lld%lld%lld", &u, &v, &a, &b, &c); 93 a = a * 2; 94 b = b * 2; 95 c = c * 2; 96 sum += a + b + c; 97 A = (a + b) / 2; 98 C = (c + b) / 2; 99 E = -b + (a + c) / 2; 100 G.add(s, u, A); 101 G.add(s, v, A); 102 G.add(u, t, C); 103 G.add(v, t, C); 104 G.add(v, u, E); 105 G.add(u, v, E); 106 } 107 ans = G.dinic(s, t); 108 printf("%lld ", (sum-ans)/2); 109 } 110 }
1 //UVALive7461 - Separating Pebbles 判断两个凸包相交 2 3 #include <bits/stdc++.h> 4 using namespace std; 5 typedef long long ll; 6 typedef pair<ll,ll> pii; 7 const ll inf = 0x3f3f3f3f; 8 const ll N =1e5+10; 9 const double eps = 1e-8; 10 ll sgn(double x) { 11 if(fabs(x) < eps)return 0; 12 if(x < 0)return -1; 13 else return 1; 14 } 15 16 struct Point { 17 ll x,y; 18 Point() {} 19 Point(ll _x,ll _y) { 20 x = _x; 21 y = _y; 22 } 23 Point operator -(const Point &b)const { 24 return Point(x - b.x,y - b.y); 25 } 26 ll operator ^(const Point &b)const { 27 return x*b.y - y*b.x; 28 } 29 ll operator *(const Point &b)const { 30 return x*b.x + y*b.y; 31 } 32 friend ll dis2(Point a) { 33 return a.x*a.x+a.y*a.y; 34 } 35 friend bool operator<(const Point &a,const Point &b){ 36 if(fabs(a.y-b.y)<eps) return a.x<b.x; 37 return a.y<b.y; 38 } 39 }; 40 typedef Point Vector; 41 double Dot(Point A, Point B){return A.x*B.x+A.y*B.y;}//点积 42 double Cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;}//叉积 43 double Length(Vector A){return sqrt(Dot(A,A));}//OA长 44 double Angle(Point A,Point B){return acos(Dot(A,B)/Length(A)/Length(B));}//OA和OB的夹角 45 //判断线段相交,不在端点相交 46 bool SegmentProperllersection(Point a1,Point a2,Point b1,Point b2){ 47 double c1=Cross(a2-a1,b1-a1),c2=Cross(a2-a1,b2-a1),c3=Cross(b2-b1,a1-b1),c4=Cross(b2-b1,a2-b1); 48 return sgn(c1)*sgn(c2)<0&&sgn(c3)*sgn(c4)<0; 49 } 50 51 ll graham(Point p[],ll n,Point q[]){ 52 ll top=1; 53 sort(p,p+n); 54 if(n==0) return 0; 55 q[0]=p[0]; 56 if(n==1) return 1; 57 q[1]=p[1]; 58 if(n==2) return 2; 59 q[2]=p[2]; 60 for(ll i=2;i<n;i++){ 61 while(top&&(Cross(q[top]-q[top-1],p[i]-q[top-1])<=0)) top--; 62 q[++top]=p[i]; 63 } 64 ll len=top; 65 q[++top]=p[n-2]; 66 for(ll i=n-3;i>=0;i--){ 67 while(top!=len&&(Cross(q[top]-q[top-1],p[i]-q[top-1])<=0)) top--; 68 q[++top]=p[i]; 69 } 70 return top; 71 } 72 73 bool C_S(Point *ch1,ll t1,Point *ch2,ll t2)//判断凸包是否相交 74 { 75 double angle[1010],x; 76 ll i,j,k,m; 77 if(t1==1)return true; 78 if(t1==2) 79 { 80 for(i=0;i<t2;i++) 81 { 82 k=sgn(Cross(ch1[1]-ch1[0],ch2[i]-ch1[0])); 83 if(k==0&&Dot(ch1[1]-ch1[0],ch2[i]-ch1[0])>0) 84 { 85 if(Length(ch2[i]-ch1[0])<Length(ch1[1]-ch1[0]))break; 86 } 87 } 88 if(i<t2)return false; 89 if(t2==2&&SegmentProperllersection(ch1[0],ch1[1],ch2[0],ch2[1]))return false; 90 return true; 91 } 92 angle[0]=0; 93 for(i=2;i<t1;i++) 94 angle[i-1]=Angle(ch1[1]-ch1[0],ch1[i]-ch1[0]); 95 for(i=0;i<t2;i++) 96 { 97 j=sgn(Cross(ch1[1]-ch1[0],ch2[i]-ch1[0])); 98 if(j<0||(j==0&&Dot(ch1[1]-ch1[0],ch2[i]-ch1[0])<0))continue; 99 j=sgn(Cross(ch1[t1-1]-ch1[0],ch2[i]-ch1[0])); 100 if(j>0||(j==0&&Dot(ch1[t1-1]-ch1[0],ch2[i]-ch1[0])<0))continue; 101 x=Angle(ch1[1]-ch1[0],ch2[i]-ch1[0]); 102 m=lower_bound(angle,angle+t1-1,x)-angle; 103 if(m==0)j=0; 104 else j=m-1; 105 k=sgn(Cross(ch1[j+1]-ch2[i],ch1[j+2]-ch2[i])); 106 if(k>=0)break; 107 } 108 if(i<t2)return false; 109 return true; 110 } 111 112 Point p1[300],p2[300],ch1[300],ch2[300]; 113 int main(){ 114 ll T; 115 scanf("%lld",&T); 116 while(T--){ 117 ll n; 118 scanf("%lld",&n); 119 ll cnt1=0,cnt2=0; 120 for(ll i=0;i<n;i++){ 121 ll x,y,c; 122 scanf("%lld%lld%lld",&x,&y,&c); 123 if(c==1){ 124 p1[cnt1++]=Point(x,y); 125 } 126 else p2[cnt2++]=Point(x,y); 127 } 128 ll t1=graham(p1,cnt1,ch1); 129 ll t2=graham(p2,cnt2,ch2); 130 if(C_S(ch1,t1,ch2,t2)&&C_S(ch2,t2,ch1,t1)) printf("Successful! "); 131 else printf("Infinite loop! "); 132 } 133 }