【2019.8.30】Za

Za 2019.8.30

SDOI2011 计算器

[BZOJ2242] [luoguP2485]

1、给定y、z、p&＃xff0c;计算y^z mod p 的值&＃xff1b;

2、给定y、z、p&＃xff0c;计算满足xy ≡z(mod p)的最小非负整数x&＃xff1b;

3、给定y、z、p&＃xff0c;计算满足y^x ≡z(mod p)的最小非负整数x。

第一个要求直接快速幂

第二个要求因为保证P为质数 直接费马小定理求逆元然后*z

第三个就是BSGS模板

&＃61;&＃61;打的时候1mol错 要注意该加括号的就加括号 不要图简便啥的不加 然后就long long

#include
#include
#include
#include
#include
#include
#include

luogu4884 多少个1&＃xff1f;

给定整数\(K\)和质数\(m\)&＃xff0c;求最小的正整数\(N\)&＃xff0c;使得 \(1111⋯1(N个1)\equiv K(mod\;m)\)

说人话&＃xff1a;就是\(111...1111\; mod\;m &＃61;K\)

将\(1111⋯1(N个1)\)乘9得\(9999⋯9(N个9)\)再\(&＃43;1\)得\(10^N\)

即求x使得\(10^x\equiv K*9&＃43;1(mod\;m)\)

题解里的玄学快速乘

好像noip啥的不支持_int128 那就先不学了

#include
#include
#include
#include
#include
#include
#include

exbsgs

银河英雄传说

重新打了一遍

带权并查集

#include
#include
#include
#include
#include
using namespace std;
#define Abs(x) ((x)<0?-(x):(x))
const int N&＃61;30000&＃43;5,M&＃61;20000&＃43;5,INF&＃61;1e9&＃43;7,inf&＃61;0x3f3f3f3f;
int n,f[N];
template void rd(t &x){x&＃61;0;int w&＃61;0;char ch&＃61;0;while(!isdigit(ch)) w|&＃61;ch&＃61;&＃61;&＃39;-&＃39;,ch&＃61;getchar();while(isdigit(ch)) x&＃61;(x<<1)&＃43;(x<<3)&＃43;(ch^48),ch&＃61;getchar();x&＃61;w?-x:x;
}int d[N],sz[N];
int find(int x){if(x&＃61;&＃61;f[x]) return x;int rt&＃61;find(f[x]);d[x]&＃43;&＃61;d[f[x]];return f[x]&＃61;rt;
}
void Merge(int x,int y){f[x&＃61;find(x)]&＃61;y&＃61;find(y),d[x]&＃61;sz[y],sz[y]&＃43;&＃61;sz[x];
}int main(){freopen("in.txt","r",stdin);int T,x,y;char opt[5];rd(T);for(int i&＃61;1;i<&＃61;30000;&＃43;&＃43;i) f[i]&＃61;i,sz[i]&＃61;1;while(T--){scanf("%s",opt);rd(x),rd(y);if(opt[0]&＃61;&＃61;&＃39;M&＃39;) Merge(x,y);else{if(find(x)!&＃61;find(y)) puts("-1");else printf("%d\n",Abs(d[x]-d[y])-1);}}return 0;
}

1930来的先生

卿卿吾愛&＃xff0c;見字如晤&＃xff1a;
　　體無恙否&＃xff1f;心安樂否&＃xff1f;藝人之工作順利否&＃xff1f;
　　屈指算來&＃xff0c;吾與汝七日未見&＃xff0c;人言一日不見&＃xff0c;如隔三秋&＃xff0c;七日之長&＃xff0c;煎熬甚苦。人生苦短如斯&＃xff0c;言語小恚&＃xff0c;便有這許多煎熬&＃xff0c;若他日真作計較&＃xff0c;又當何以自處&＃xff1f;思來想去&＃xff0c;日夜翻覆&＃xff0c;更覺會日何短&＃xff0c;隔日何長&＃xff1f;憂思何繁&＃xff0c;歡顏何驟&＃xff1f;
　　吾心愛汝&＃xff0c;願見歡顏&＃xff0c;恨吾怨吾&＃xff0c;皆吾自取。當日失言&＃xff0c;悔之不及。前日電訊致歉&＃xff0c;卿定有閱之&＃xff0c;閱而不復&＃xff0c;非卿之過&＃xff0c;是吾書未達意&＃xff0c;辭未達情。游目天地&＃xff0c;何以悅卿&＃xff1f;雖天涯海角&＃xff0c;卿所樂之&＃xff0c;吾必往之&＃xff0c;幽王癡情&＃xff0c;敢笑薄之——此等甘辭蜜語&＃xff0c;不能訴吾衷情于一二&＃xff0c;卿心明澈&＃xff0c;願可鑒之。
　　論愛侶之屬&＃xff0c;愛之尤甚&＃xff0c;怨懟尤多&＃xff0c;相思酷刑&＃xff0c;甚于斧鉞。吾與卿七日未見&＃xff0c;此卿卿于吾小懲大誡&＃xff0c;吾必銘記於心&＃xff0c;定無再犯。昨日歸家途中&＃xff0c;見有春梅余香枝頭&＃xff0c;衷情難表&＃xff0c;癡意難訴&＃xff0c;春意兩瓣&＃xff0c;托于鴻雁。東君有意&＃xff0c;顧惜芳春&＃xff0c;卿卿當如東君&＃xff0c;顧惜吾心。
　　最后一张纸只有两行正楷大字&＃xff1a;
　　以上那些我知你必定看不懂&＃xff0c;只看這最後兩句罷&＃xff1a;我在你樓下等你&＃xff0c;一起去閱江樓吃龍蝦。

[USACO]道路与航线

[BZOJ2200] [luoguP3008]

咕了&＃xff01;

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef pairpii;
const int N&＃61;25000&＃43;5,M&＃61;50000&＃43;5,INF&＃61;1e9&＃43;7,inf&＃61;0x3f3f3f3f;
int n,r,p,s,in[N];
template void rd(t &x){x&＃61;0;int w&＃61;0;char ch&＃61;0;while(!isdigit(ch)) w|&＃61;ch&＃61;&＃61;&＃39;-&＃39;,ch&＃61;getchar();while(isdigit(ch)) x&＃61;(x<<1)&＃43;(x<<3)&＃43;(ch^48),ch&＃61;getchar();x&＃61;w?-x:x;
}int hd[N],tt&＃61;1;
struct edge{int v,w,nxt;}e[M<<2];
void add(int u,int v,int w){e[&＃43;&＃43;tt]&＃61;(edge){v,w,hd[u]},hd[u]&＃61;tt;
}int bl[N],cnt&＃61;0;
vectorblo[N];
void dfs(int u){bl[u]&＃61;cnt,blo[cnt].push_back(u);for(int i&＃61;hd[u],v;i;i&＃61;e[i].nxt)if(!bl[v&＃61;e[i].v]) dfs(v);
}int dis[N];bool vis[N];
void topsort(){memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));queueQ;dis[s]&＃61;0;//,Q.push((bl[s]))for(int i&＃61;1;i<&＃61;cnt;&＃43;&＃43;i) if(!in[i]) Q.push(i);priority_queue,greater >q;while(!Q.empty()){int k&＃61;Q.front();Q.pop();for(int i&＃61;0,x;idis[u]&＃43;(w&＃61;e[i].w)){dis[v]&＃61;dis[u]&＃43;w;if(bl[v]&＃61;&＃61;bl[u]) q.push((make_pair(dis[v],v)));}if(bl[u]!&＃61;bl[v]&&!(--in[bl[v]])) Q.push(bl[v]);}}}
}int main(){freopen("in.txt","r",stdin);rd(n),rd(r),rd(p),rd(s);for(int i&＃61;1,u,v,w;i<&＃61;r;&＃43;&＃43;i) rd(u),rd(v),rd(w),add(u,v,w),add(v,u,w);for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) if(!bl[i]) &＃43;&＃43;cnt,dfs(i);for(int i&＃61;1,u,v,w;i<&＃61;p;&＃43;&＃43;i)rd(u),rd(v),rd(w),add(u,v,w),&＃43;&＃43;in[bl[v]];topsort();for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i)if(dis[i]>&＃61;1e9) puts("NO PATH");else printf("%d\n",dis[i]);return 0;
}

USACO cow relays

#include
#include
#include
#include
#include
#include
#include