2024-03-21
Grass Cownoisseur G
上周没写完的题
分析过思路了，直接放码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=100100,M=2*N;
int n,m;
int hd[N],edg[N],nxt[N],idx;
void adde(int u,int v) {
edg[idx]=v,nxt[idx]=hd[u],hd[u]=idx++;
}
pair<int,int> es[N];
vector<int> G[M];
int scc[N],siz[M],cnt;
int dfn[N],low[N],idt;
int stk[N],top;
bool ins[N];
void Tarjan(int u) {
dfn[u]=low[u]=++idt;
stk[++top]=u,ins[u]=true;
for(int i=hd[u];~i;i=nxt[i]) {
int v=edg[i];
if(!dfn[v]) {
Tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v]) low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]) {
cnt++;
while(stk[top]!=u) {
scc[stk[top]]=cnt;
siz[cnt]++;
ins[stk[top]]=false;
top--;
}
scc[u]=cnt;
siz[cnt]++;
ins[u]=false;
top--;
}
}
int dist[M];
bool inq[M];
void spfa() {
queue<int> que;
que.push(scc[1]);
inq[scc[1]]=true;
while(!que.empty()) {
int u=que.front();
que.pop();
inq[u]=false;
for(int i=0;i<G[u].size();i++) {
int v=G[u][i];
if(dist[v]<dist[u]+siz[u]) {
dist[v]=dist[u]+siz[u];
if(!inq[v]) {
que.push(v);
inq[v]=true;
}
}
}
}
}
int main() {
memset(hd,-1,sizeof(hd));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) {
int u,v;
scanf("%d%d",&u,&v);
adde(u,v);
es[i].first=u,es[i].second=v;
}
for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i);
for(int i=1;i<=cnt;i++) siz[i+cnt]=siz[i];
for(int i=1;i<=m;i++) {
int u=es[i].first,v=es[i].second;
if(scc[u]==scc[v]) continue;
G[scc[u]].push_back(scc[v]);
G[scc[u]+cnt].push_back(scc[v]+cnt);
G[scc[v]].push_back(scc[u]+cnt);
}
G[scc[1]].push_back(scc[1]+cnt);
spfa();
printf("%d\n",dist[scc[1]+cnt]);
return 0;
}
听课的时候老师讲的
终于知道 C++ 负数取模是负数的原因了
因为 C++ 整除是 向 0 取整 Python 等 是 向负无穷取整
意思就是 C++ 向靠近 0 的那边取整
eg:
C++: 5/3=1 -5/3=-1
Python: 5/3=1 -5/3=-2
说唱
上周考试不会的题，改改
首先理解 \(f(x)\) 是什么意思
例如 \(x=2134\) 那么 \(f(x)=2134+213+21+2\)
换一个形式 \(f(x)=2222+111+33+4\)
我们发现，对于从右往左数第 \(k\) 个数字 \(a_k\) 它对 \(f(x)\) 的贡献是
等比数列求和一下，其实就是
\[\frac{(10^k-1)\times a_k}{9} \]把所有位的贡献加起来，得到
\[y=f(x)=\frac{10x-S}{9} \]其中 \(S\) 是 \(x\) 所有位上数字之和
整理一下
我们记 \(p=10x\) 从第一个大于等于 \(9y\) 的 \(10\) 的倍数开始枚举 \(p\)
注意到 \(x\) 的数字之和就是 \(p\) 的数字之和
每次 \(p\) 加十的时候更新 \(S\) ，再记录 \(p-9y\) 为 \(D\)
若某一时刻 \(S\) 与 \(D\) 相等就得到答案
如果一直枚举到 \(D\) 比 n 位数字所能达到的最大的数字和 \(9n\) 还大都没有找到答案，说明无解
时间复杂度 \(O(n)\)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6e5+10;
char s[N];
int x[N],y[N];
int D;
int S;
int n;
int main() {
int T;
scanf("%d",&T);
while(T--) {
memset(x,0,sizeof(x));
memset(y,0,sizeof(y));
D=0,S=0;
scanf("%s",s+1);
n=strlen(s+1);
int nn=n;
for(int i=1;i<=n;i++) y[i]=s[n-i+1]-'0',x[i]=y[i]*9;
if(nn==1&&y[1]==0) {
puts("0");
continue;
}
for(int i=1;i<=n;i++) x[i+1]+=x[i]/10,x[i]%=10;
while(x[n+1]>9) x[n+2]+=x[++n]/10,x[n]%=10;
n+=(x[n+1]>0);
int p=1;
D+=10-x[p],x[p]+=10-x[p];
while(x[p]>9) x[p+1]+=x[p]/10,x[p]%=10,p++;
n=max(n,p);
for(int i=1;i<=n;i++) S+=x[i];
bool flg=false;
while(D<=9*nn) {
if(S==D) {
for(int i=n;i>1;i--) printf("%d",x[i]);
puts("");
flg=true;
break;
}
D+=10;
int p=2;
x[p]++;
while(x[p]>9) x[p+1]+=x[p]/10,x[p]%=10,p++;
n=max(n,p);
S-=9*(p-2),S++;
}
if(!flg) puts("-1");
}
return 0;
}
ztx 的玄学方法（不知道正不正确）
- 原题中的递归式如果不向下取整，y=x*10/9，则 x=y*0.9
- 加上取整误差不超过 \(\log x\) 也就是位数 n
- f(x) 单调增，可以二分
复杂度 \(O(n\log n)\)
扩展中国剩余定理
数学专题题单上面的
发现自己 72 分
update: 原因是要开 _int128……
exCRT
对于两个方程
\[\left\{\begin{matrix} x\equiv r_1 \ (\bmod \ p_1) \\ x\equiv r_2 \ (\bmod \ p_2) \end{matrix}\right. \]考虑怎么合并
写成带余除法的形式
移项得到
\[k_1\times p_1-k_2\times p_2=r_2-r_1 \]用 exgcd 求出 k1 的最小正整数解
新的方程为
其中$$R=k_1\times p_1+r_1 \ \ \ M=lcm(p_1,p_2)$$
n个方程，两两合并 n-1 次
最后的 R 就是答案
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef __int128 i128;
int n;
ll pin,rin;
i128 exgcd(i128 a,i128 b,i128 &x,i128 &y) {
if(b==0) {
x=1,y=0;
return a;
}
i128 d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
int main() {
scanf("%d",&n);
scanf("%lld%lld",&pin,&rin);
i128 p1=pin,r1=rin;
for(int i=1;i<n;i++) {
scanf("%lld%lld",&pin,&rin);
i128 p2=pin,r2=rin;
i128 k1,k2;
i128 d=exgcd(p1,p2,k1,k2);
i128 g=r2-r1;
if(g%d!=0) {
puts("-1");
return 0;
}
k1=((k1*g/d)%(p2/d)+(p2/d))%(p2/d);
r1+=p1*k1,p1=(p1*p2)/d;
}
printf("%lld\n",r1);
return 0;
}
荒岛野人
原题等价于
给定 \(C_1,C_2,\dots,C_n \ \ \ P_1,P_2,\dots,P_n \ \ \ L_1,L_2,\dots,L_n\)
求最小的 M ，使得对于任意一对 \(i,j\) ，同余方程 \(C_i+xP_i\equiv C_j+xP_j \ (\bmod \ M)\) 都无解或最小正整数解大于 \(\min(L_i,L_j)\)
方程可以化为
从 \(\max C_i\) 开始枚举 \(M\)
然后枚举所有的 \((i,j)\) 用 exgcd 求出最小的正整数解
如果有符合条件的解，那么当前的 M 不行
如果所有 \(n^2\) 个方程都在范围内无解，输出当前的 M
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=17;
int n;
int c[N],p[N],l[N];
int exgcd(int a,int b,int &x,int &y) {
if(b==0) {
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return d;
}
bool check(int M) {
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
if(i==j) continue;
if(p[i]<p[j]) continue;
int A=p[i]-p[j],B=c[j]-c[i];
int x,y;
int d=exgcd(A,M,x,y);
if(B%d==0) {
x=((x*(B/d))%(M/d)+(M/d))%(M/d);
if(x<=min(l[i],l[j])) return false;
}
}
}
return true;
}
int main() {
scanf("%d",&n);
int m=0;
for(int i=1;i<=n;i++) scanf("%d%d%d",&c[i],&p[i],&l[i]),m=max(m,c[i]);
while(true) {
if(check(m)) {
printf("%d\n",m);
break;
}
m++;
}
return 0;
}
古代猪文
Lucas定理
若 p 是质数
则
# 题意简述 #
计算
# Solution #
数学全家桶
欧拉定理 + 卢卡斯定理 + 中国剩余定理 + 快速幂
- \(999911659\) 是质数 根据欧拉定理 就是要算 \(g^{\sum_{k\mid n}{n\choose k}\bmod 999911658}\bmod 999911659\)
考虑如何计算 \(\sum_{k\mid n}{n\choose k}\bmod 999911658\)
- \(999911658=2\times3\times4679\times35617\)
有些题的模数比较奇怪的时候可以分解一下看看可能会有特殊性质
-
Lucas 求出 \(\sum_{k\mid n}{n\choose k}\) 模每个小质数的结果 \(r_i\)
-
然后中国剩余定理求解同余方程组
得出 \(\sum_{k\mid n}{n\choose k}\bmod 999911658\)
- 最后快速幂就行
#include<iostream>
#include<cstring>
#include<algorithm>
#define mod 999911658
using namespace std;
typedef long long ll;
const int dd[4]={2,3,4679,35617};
ll n,g;
ll frac[99999];
ll qpow(ll a,ll k,ll p) {
ll res=1;
while(k) {
if(k&1) res=res*a%p;
a=a*a%p,k>>=1;
}
return res;
}
ll C(ll x,ll y,ll p) {
if(x<y) return 0;
return frac[x]*qpow(frac[y],p-2,p)%p*qpow(frac[x-y],p-2,p)%p;
}
ll Lucas(ll x,ll y,ll p) {
if(y==0) return 1;
return C(x%p,y%p,p)*Lucas(x/p,y/p,p)%p;
}
void init(ll x) {
frac[0]=1;
for(ll i=1;i<=x;i++) frac[i]=frac[i-1]*i%x;
}
int r[5];
int main() {
scanf("%lld%lld",&n,&g);
if(g%(mod+1)==0) {
puts("0");
return 0;
}
ll h=0;
for(int i=0;i<4;i++) {
ll D=dd[i];
init(D);
for(ll d=1;d*d<=n;d++) {
if(n%d!=0) continue;
r[i]=(r[i]+Lucas(n,d,D))%D;
if(d*d==n) continue;
r[i]=(r[i]+Lucas(n,n/d,D))%D;
}
h=(h+r[i]*(mod/D)%mod*qpow(mod/D,D-2,D)%mod)%mod;
}
printf("%lld\n",qpow(g,h,mod+1));
return 0;
}
标签：03,21,10,int,ll,2024,++,include,bmod From： https://www.cnblogs.com/Orange-Star/p/18086782需要注意的点：
- 组合数 C(n,m) 在 n<m 的时候要返回 0（不然会RE）
- g 是模数的倍数的时候特判输出 0
- frac 不能 一开始初始化，各个函数的模数也不能用全局的，而是要传参数，因为 4 个模数情况都不一样要单独考虑