网站建设需要了解什么,主流软件开发平台,佛山个人建站模板,深圳有什么互联网公司CF40E
题目链接
点击打开链接
题目解法
首先#xff0c;如果 n , m n,m n,m 一奇一偶#xff0c;那么答案为 0 0 0 原因是从行和列的角度分析#xff0c; − 1 -1 −1 个数的奇偶性不同
可以发现 k max { n , m } k\max\{n,m\} kmax{n,m} 的性质很微…CF40E
题目链接
点击打开链接
题目解法
首先如果 n , m n,m n,m 一奇一偶那么答案为 0 0 0 原因是从行和列的角度分析 − 1 -1 −1 个数的奇偶性不同
可以发现 k max { n , m } k\max\{n,m\} kmax{n,m} 的性质很微妙把它转化为有用的信息即为 令 n m nm nm则必有一行为空 可以发现除了空行其他所有行只需在满足行乘积为 − 1 -1 −1 的情况下随便填然后令空行满足列的限制即可 我们需要考虑空行在满足列的限制的情况下是否仍然满足行的限制这个对 − 1 -1 −1 的个数讨论一下不难证得
于是可以简单地计算时间复杂度 O ( n 2 ) O(n^2) O(n2)
#include bits/stdc.h
using namespace std;
const int N1100;
int n,m,k,dp[N][N],pw[N];
int cov1[N],cov2[N];
int od1[N],od2[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int main(){nread(),mread(),kread();if((nm)1){ puts(0);exit(0);}for(int i1;ik;i){int xread(),yread(),zread();cov1[x],cov2[y];if(z-1) od1[x]^1,od2[y]^1;}int Pread();for(int i1;in;i) if(cov1[i]m!od1[i]){ puts(0);exit(0);}for(int i1;im;i) if(cov2[i]n!od2[i]){ puts(0);exit(0);}pw[0]1;for(int i1;imax(n,m);i) pw[i]pw[i-1]*2%P;if(nm){for(int i1;in;i)if(!cov1[i]){int ans1;for(int j1;jn;j){if(ij) continue;if(m-cov1[j]0) ans1ll*ans*pw[m-cov1[j]-1]%P;}printf(%d,ans);exit(0);}}elsefor(int i1;im;i)if(!cov2[i]){int ans1;for(int j1;jm;j){if(ij) continue;if(n-cov2[j]0) ans1ll*ans*pw[n-cov2[j]-1]%P;}printf(%d,ans);exit(0);}return 0;
}
CF140E
题目链接
点击打开链接
题目解法
先特殊提醒一下每一层的球不是构成一个环而是一个序列 可以发现这一层只关心选了几个颜色而不关心选了那些颜色 所以显然有 d p i , j dp_{i,j} dpi,j 为到第 i i i 层第 i i i 层有 j j j 个颜色的方案数 考虑转移 容斥一下用总的方案数 - 不合法的方案数 所以 d p i , j m j ‾ ∗ f l [ i ] , j ∑ d p i − 1 , k − j ! ∗ d p i − 1 , j dp_{i,j}m^{\underline{j}}*f_{l[i],j}\sum{dp_{i-1,k}}-j!*dp_{i-1,j} dpi,jmj∗fl[i],j∑dpi−1,k−j!∗dpi−1,j 其中 f i , j f_{i,j} fi,j 为长度为 i i i 序列相邻不同颜色总数为 j j j且每一种颜色都染过的方案数 f i , j f_{i,j} fi,j 好求不细讲了直接给转移式子 f i , j f i − 1 , j − 1 f i − 1 , j ∗ ( j − 1 ) f_{i,j}f_{i-1,j-1}f_{i-1,j}*(j-1) fi,jfi−1,j−1fi−1,j∗(j−1) 因为没有规定染 m m m 个颜色中的哪 j j j 个所以要乘 m j ‾ m^{\underline{j}} mj 减去的数中因为之前已经规定好了选哪 j j j 个所以只需要给 j j j 个数排个次序即可不难发现 f f f 式子中并没有规定 j j j 个颜色的顺序 时间复杂度 O ( n 2 ) O(n^2) O(n2)
#include bits/stdc.h
using namespace std;
const int MX5100,N1000100;
int n,m,P,l[N];
int fac[MX],perm[N];
int dp[2][MX],f[MX][MX];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int main(){nread(),mread(),Pread();for(int i1;in;i) l[i]read();fac[0]1;for(int i1;iMX;i) fac[i]1ll*fac[i-1]*i%P;perm[0]1;for(int i1;im;i) perm[i]1ll*perm[i-1]*(m-i1)%P;f[0][0]1;for(int i1;iMX;i) for(int j1;ji;j) f[i][j](f[i-1][j-1]1ll*f[i-1][j]*(j-1))%P;int sum0;for(int i1;il[1];i) dp[1][i]1ll*perm[i]*f[l[1]][i]%P,sum(sumdp[1][i])%P;for(int i2;in;i){for(int j1;jl[i];j) dp[i1][j]0;for(int j1;jl[i];j){dp[i1][j]1ll*perm[j]%P*sum%P*f[l[i]][j]%P;if(jl[i-1]) dp[i1][j](dp[i1][j]-1ll*dp[~i1][j]*fac[j]%P*f[l[i]][j]%PP)%P;}sum0;for(int j1;jl[i];j) sum(sumdp[i1][j])%P;}printf(%d,sum);return 0;
}
CF482D
题目链接
点击打开链接
题目解法
显然树形 d p dp dp 考虑染的颜色只跟染的顺序的奇偶性有关 所以令 d p i , 0 / 1 dp_{i,0/1} dpi,0/1 表示在 i i i 的子树中选了偶数还是奇数个点 考虑编号升序是好转移的编号降序的方案和编号升序的方案一样 现在只需要计算编号升序和降序重复的方案数 不难发现重复的条件为 ∀ p r e i − 1 ≡ s u f i 1 \forall pre_{i-1}\equiv suf_{i1} ∀prei−1≡sufi1 可以发现这个等价于
每个子树中选的点都为偶数每个子树中选的点都为奇数且只有奇数个子树选到
这个可以在开一个 d p dp dp 数组 f i , 0 / 1 , 0 / 1 f_{i,0/1,0/1} fi,0/1,0/1 表示在 i i i 的子树中选出了奇数或偶数个点所有选的子树中点数均为奇数或偶数不难转移
时间复杂度 O ( n 2 ) O(n^2) O(n2)
#include bits/stdc.h
using namespace std;
const int N100100,P1e97;
int n,dp[N][2],f[N][2][2];
vectorint vec[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void dfs(int u){dp[u][1]1,f[u][0][0]f[u][0][1]1;for(int v:vec[u]){dfs(v);int t0dp[u][0],t1dp[u][1];dp[u][0](1ll*t0*dp[v][0]1ll*t1*dp[v][1])%P;dp[u][1](1ll*t0*dp[v][1]1ll*t1*dp[v][0])%P;t0f[u][1][1],t1f[u][0][1];f[u][0][0](f[u][0][0]1ll*f[u][0][0]*(dp[v][0]-1))%P;//子树中选了偶数个点所有选的子树中都选了偶数个点f[u][0][1](f[u][0][1]1ll*t0*dp[v][1])%P;//子树中选了偶数个点所有选的子树中都选了奇数个点f[u][1][1](f[u][1][1]1ll*t1*dp[v][1])%P;//子树中选了奇数个点所有选的子树中都选了奇数个点}dp[u][0](dp[u][0]*21)%P,dp[u][1]dp[u][1]*2%P;dp[u][0](dp[u][0]-f[u][1][1]P)%P,dp[u][1](dp[u][1]-f[u][0][0]P)%P;
}
int main(){nread();for(int i2;in;i) vec[read()].push_back(i);dfs(1);printf(%d,(dp[1][0]dp[1][1]-1)%P);return 0;
}
CF325E
题目链接
点击打开链接
题目解法
先考虑 n n n 为偶数的情况 先看一个比较妙的性质对于 i i i 和 i n 2 i\frac{n}{2} i2n它们能到达的两个点是一样的因为 2 i ≡ 2 i n 2i\equiv2in 2i≡2in 且 2 i 1 ≡ 2 i n 1 2i1\equiv 2in1 2i1≡2in1 所以考虑暂时钦定 i i i 连向 2 i 2i 2i i n 2 i\frac{n}{2} i2n 连向 2 i 1 2i1 2i1 考虑这样整张图会形成若干个简单环现在需要考虑合并简单环 若 x x x 和 x n 2 x\frac{n}{2} x2n 不在一个简单环内那么考虑把 x x x 连到 2 x 1 2x1 2x1 x n 2 x\frac{n}{2} x2n 连到 2 x 2x 2x这样可以把 2 2 2 个环合并成一个环这个可以用并查集维护
考虑 n n n 为奇数的情况直觉告诉我们一定是无解的 考虑来证明它可以发现到终点 0 0 0 的点只能是 n − 1 2 \frac{n-1}{2} 2n−1而到达 n − 1 n-1 n−1 的点也只能是 n − 1 2 \frac{n-1}{2} 2n−1这就矛盾了 时间复杂度 O ( n ) O(n) O(n)
#include bits/stdc.h
using namespace std;
const int N100100;
int n,fa[N],rt,nxt[N];
bool vis[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void dfs(int u){vis[u]1,fa[u]rt;if(!vis[nxt[u]]) dfs(nxt[u]);
}
int get_father(int x){ return xfa[x]?x:fa[x]get_father(fa[x]);}
int main(){nread();if(n1){ puts(-1);exit(0);}for(int i0;in/2;i) nxt[i]i1,nxt[in/2]i1^1;for(int i0;in;i) fa[i]i;for(int i0;in;i) if(!vis[i]) rti,dfs(i);for(int i0;in/2;i){int xget_father(i),yget_father(in/2);if(x!y) fa[x]y,nxt[i]i1^1,nxt[in/2]i1;}int pos0;while(nxt[pos]) printf(%d ,pos),posnxt[pos];printf(%d 0,pos);return 0;
}
CF896D
题目链接
点击打开链接
题目解法
先考虑 n n n 个人不包含 v i p vip vip 的情况 考虑转化把 50 50 50 元看成 1 1 1 100 100 100 元看成 − 1 -1 −1 题目就是问有多少种方案所有的前缀和都 ≥ 0 \ge 0 ≥0 这让我们想到了卡特兰数于是可以考虑用推卡特兰数的方法来推到 ( x , n − x ) (x,n-x) (x,n−x) 处的方案数条件是 n − x l ≤ x ≤ n − x r n-xl\le x\le n-xr n−xl≤x≤n−xr 推断方法不细讲大概就是对 y x 1 yx1 yx1 作对称最后推出来的式子应该是 ( n x ) − ( n x 1 ) \binom{n}{x}-\binom{n}{x1} (xn)−(x1n)
然后考虑有 v i p vip vip 的情况即枚举个数最终的答案即为 ∑ i 0 n ∑ i − x l ≤ x ≤ i − x r ( i x ) − ( i x 1 ) \sum\limits_{i0}^{n}\sum\limits_{i-xl\le x\le i-xr}\binom{i}{x}-\binom{i}{x1} i0∑ni−xl≤x≤i−xr∑(xi)−(x1i) 可以发现对于同一个 i i i中间的组合数都可以消掉所以只要算最左边和最右边的组合数即可
考虑 P P P 不是质数我们可以把 p p p 质因数分解然后把每个计算的数拆分成 x ∗ ∏ p k α k x*\prod p_k^{\alpha_k} x∗∏pkαk其中 ( x , P ) 1 (x,P)1 (x,P)1这个对每个 p p p 的质因子开个桶即可考虑 P P P 的质因子不会超过 9 个所以可以很快维护
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
#include bits/stdc.h
#define int long long
using namespace std;
const int N100100;
int n,P,l,r;
int phi,pr[N],cnt;
int fac[N],invX[N],coef[N][35];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int qmi(int a,int b){int res1;for(;b;b1){if(b1) res1ll*res*a%P;a1ll*a*a%P;}return res;
}
void calc(){fac[0]invX[0]1,fac[1]invX[1]1;for(int i2;in;i){int ti;for(int j1;jcnt;j){coef[i][j]coef[i-1][j];while(t%pr[j]0) t/pr[j],coef[i][j];}fac[i]1ll*fac[i-1]*t%P;invX[i]qmi(fac[i],phi-1);}
}
int binom(int x,int y){if(xy) return 0;int resfac[x]*invX[y]%P*invX[x-y]%P;for(int i1;icnt;i) resres*qmi(pr[i],coef[x][i]-coef[y][i]-coef[x-y][i])%P;return res;
}
signed main(){nread(),Pread(),lread(),rread();phiP;int tP;for(int i2;i*it;i)if(t%i0){while(t%i0) t/i;pr[cnt]i,phiphi/i*(i-1);}if(t1) pr[cnt]t,phiphi/t*(t-1);calc();int ans0;for(int i0;in;i){int lb(li1)/2;int rbmin((ri)/2,i);if(lbrb) ans(ans(binom(i,lb)-binom(i,rb1)P)*binom(n,i)%P)%P;}printf(%lld,ans);return 0;
}
CF750G
题目链接
点击打开链接
题目解法
考虑对答案的路径分 3 种情况
一个点方案数为 1从祖先到子孙的路径 令祖先的编号为 u u u延续到下面的深度为 h h h 则编号和为 ( 2 h 1 − 1 ) ∗ u ∑ i 0 h − 1 ( 2 i − 1 ) ∗ c i (2^{h1}-1)*u\sum_{i0}^{h-1} (2^i-1)*c_i (2h1−1)∗u∑i0h−1(2i−1)∗ci其中 c i c_i ci 为这条边是否往右走 考虑 ∑ i 0 h − 1 2 i ∗ c i 2 h \sum_{i0}^{h-1} 2^i*c_i2^h ∑i0h−12i∗ci2h那么枚举 h h h我们可以直接计算出对应的 u u u 然后判断是否合法即可从 u u u 到 l c a lca lca 到 v v v 的路径 u ≠ l c a ≠ v u\neq lca\neq v ulcav 令祖先的编号为 u u u延续到下面的深度分别为 h 1 , h 2 h1,h2 h1,h2 则编号和为 ( 2 h 1 1 2 h 2 1 − 2 ) ∗ u ∑ i 0 h 1 − 1 ( 2 i − 1 ) c i ∑ i 0 h 2 − 1 ( 2 i − 1 ) c i ′ (2^{h11}2^{h21}-2)*u\sum_{i0}^{h1-1}(2^i-1)c_i\sum_{i0}^{h2-1}(2^i-1)c_i (2h112h21−2)∗u∑i0h1−1(2i−1)ci∑i0h2−1(2i−1)ci′ 同理对于相同的 h 1 , h 2 h1,h2 h1,h2我们可以唯一确定出一个 u u u 那么考虑计算下面有多少种路径 考虑 2 i − 1 2^i-1 2i−1 的 − 1 -1 −1 不好计算所以考虑枚举 c i , c i ′ c_i,c_i ci,ci′ 为 1 1 1 的数的个数 然后考虑 d p dp dp令 d p i , j , 0 / 1 dp_{i,j,0/1} dpi,j,0/1 表示从低到高到了第 i i i 位已经选了 j j j 个数是否进位的方案数 这样可以轻松转移要注意 h 1 − 1 h1-1 h1−1 和 h 2 − 1 h2-1 h2−1 位要强制选和不选因为必须往左和往右
时间复杂度 O ( H 5 ) O(H^5) O(H5) H H H 为树高
#include bits/stdc.h
#define int long long
using namespace std;
int s,bs[60],dp[60][120][2];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int check(int left,int h){for(int ih;i0;i--) if(leftbs[i]-1) left-bs[i]-1;return !left;
}
int calc(int h1,int h2,int left){int res0;for(int i1;ih1h2;i){int curleftlefti;bool flg1;for(int jmax(h1,h2)2;j50;j) if(curleftj1){ flg0;break;}if(!flg||(curleft1)) continue;memset(dp,0,sizeof(dp));dp[0][0][0]1;for(int j1;jmax(h1,h2)1;j)for(int k0;ki;k)for(int z0;z1;z){if(!dp[j-1][k][z]) continue;for(int x0;x(jh1);x)for(int y(jh2);y(jh2);y){int curbit(xyz)%2,ne(xyz)/2;if(curbit!(curleftj1ll)) continue;dp[j][kxy][ne]dp[j-1][k][z];}}resdp[max(h1,h2)1][i][0];}return res;
}
signed main(){sread();bs[0]1;for(int i1;i51;i) bs[i]bs[i-1]*2;int ans1;//选n//端点u,v为祖孙关系//枚举相差层数for(int h1;h50;h){int us/(bs[h1]-1);//头if(!u) continue;if(check(s-u*(bs[h1]-1),h)) ans;}//端点u,v不是祖孙关系for(int h11;h150;h1)for(int h21;h250;h2){int us/(bs[h11]bs[h21]-3);if(!u) continue;anscalc(h1,h2,s-u*(bs[h11]bs[h21]-3));}printf(%lld,ans);return 0;
}
/*
dp[i][j][0/1]:到第i位选了j个数是否有进位的方案数
*/CF981H
题目链接
点击打开链接
题目解法
感觉挺好的一道题除了多项式 显然 k k k 条路径共同经过的部分一定是一段路径 然后考虑分类讨论路径端点 u , v u,v u,v 的关系 u , v u,v u,v 不是祖先关系 答案即为 s u × s v s_u\times s_v su×sv 其中 s u s_u su 表示在 u u u 的子树中选出 k k k 个点并组成排列的方案数 考虑枚举 u u u 节点的选择个数因为只有它是可以经过不限制次的 u u u 的儿子的子树中只能选出 1 1 1 个点 所以考虑除了 u u u 选 i i i 个点且不考虑顺序的方案数即为 [ x i ] ∏ ( 1 s i z v x ) [x^i]\prod (1siz_vx) [xi]∏(1sizvx) 因为是要求出这个多项式卷积的每一项的所以考虑用分治 n t t ntt ntt 求出 然后 s u s_u su 即为 ∑ i 0 k ( k i ) × i ! × [ x i ] ∏ ( 1 s i z v x ) \sum\limits_{i0}^{k}\binom{k}{i}\times i!\times [x^i]\prod (1siz_vx) i0∑k(ik)×i!×[xi]∏(1sizvx) 然后所有情况的答案即为 ( ∑ s u ) 2 (\sum s_u)^2 (∑su)2 还需要减去 u u u 和 u u u 自己的代价和 u u u 和 u u u 的子树内的点的代价 这用一个子树和不难求出 u , v u,v u,v 是祖先关系 这种情况稍微难办一些 不考虑 u u u 选出 i i i 个点的方案数为 [ x i ] ∑ v ∈ s o n ( u ) ( 1 ( n − s i z u ) x ) × ∏ w ≠ v ( 1 s i z w x ) [x^i]\sum\limits_{v\in son(u)}{(1(n-siz_u)x)\times \prod\limits_{w\neq v} (1siz_wx)} [xi]v∈son(u)∑(1(n−sizu)x)×wv∏(1sizwx) 这个也可以用分治 n t t ntt ntt 求出 计算答案的式子和第一类情况一样
记得特判一条路径的情况 因为度数之和为 n n n所以时间复杂度是分治 n t t ntt ntt 的 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)
#include bits/stdc.h
using namespace std;
const int N300000,P998244353;
const int G3,Gi332748118;
typedef pairvectorint,vectorint pvv;
typedef pairint,int pii;
int n,k,ans,ans2;
int rev[N],tot;
int f[N],s[N];
int siz[N],fac[N],inv[N];
vectorpii son;
vectorint vec[N],Gr[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
inline void inc(int x,int y){xy;if(xP) x-P;
}
int qmi(int a,int b){int res1;for(;b;b1){if(b1) res1ll*res*a%P;a1ll*a*a%P; }return res;
}
vectorint ntt(vectorint a,bool neg){for(int i0;itot;i) if(irev[i]) swap(a[i],a[rev[i]]);for(int mid1;midtot;mid1){int g1qmi(neg?Gi:G,(P-1)/(mid1));for(int i0;itot;imid1){int gk1;for(int j0;jmid;j,gk1ll*gk*g1%P){int xa[ij],y1ll*gk*a[ijmid]%P;a[ij]xyP?xy-P:xy,a[ijmid]x-y0?x-yP:x-y;}}}return a;
}
vectorint mul(vectorint A,vectorint B){int bit0;while((1bit)A.size()B.size()) bit;tot1bit;for(int i0;itot;i) rev[i](rev[i1]1)|((i1)(bit-1));A.resize(tot),B.resize(tot);Antt(A,0),Bntt(B,0);for(int i0;itot;i) A[i]1ll*A[i]*B[i]%P;Antt(A,1);int ivqmi(tot,P-2);for(int i0;itot;i) A[i]1ll*A[i]*iv%P;while(!A.back()) A.pop_back();return A;
}
vectorint add(vectorint A,vectorint B)if(A.size()B.size()) swap(A,B);for(int i0;iB.size();i) inc(A[i],B[i]);return A;
}
pvv pushup(pvv L,pvv R){vectorint fmul(L.first,R.first);vectorint gadd(mul(L.first,R.second),mul(L.second,R.first));return make_pair(f,g);
}
pvv solve(int l,int r){if(lr) return make_pair(vectorint{1,son[l].first},vectorint{son[l].second});int mid(lr)1;return pushup(solve(l,mid),solve(mid1,r));
}
void predfs(int u,int fa){siz[u]1;for(int v:vec[u])if(v!fa){predfs(v,u);siz[u]siz[v],Gr[u].push_back(v);}
}
int C(int a,int b){ return 1ll*fac[a]*inv[b]%P*inv[a-b]%P;}
void dfs(int u){for(int v:Gr[u]) dfs(v),inc(s[u],s[v]);if(!Gr[u].size()) f[u]s[u]1;else{son.clear();for(int v:Gr[u]) son.push_back({siz[v],s[v]});pvv retsolve(0,son.size()-1);vectorint poly1ret.first,poly2ret.second;for(int i0;imin((int)poly1.size(),k1);i) inc(f[u],1ll*poly1[i]*C(k,i)%P*fac[i]%P);inc(s[u],f[u]);poly2mul(vectorint{1,n-siz[u]},poly2);for(int i0;imin((int)poly2.size(),k1);i) inc(ans2,1ll*poly2[i]*C(k,i)%P*fac[i]%P);}inc(ans,P-1ll*f[u]*(2*s[u]%P-f[u]P)%P);
}
int main(){nread(),kread();if(k1){ printf(%d\n,(1ll*n*(n-1)/2)%P);exit(0);fac[0]1;for(int i1;in1;i) fac[i]1ll*fac[i-1]*i%P;inv[n1]qmi(fac[n1],P-2);for(int in;i0;i--) inv[i]1ll*inv[i1]*(i1)%P;for(int i1;in;i){int xread(),yread();vec[x].push_back(y),vec[y].push_back(x);}predfs(1,-1),dfs(1);inc(ans,1ll*s[1]*s[1]%P),ans1ll*ans*qmi(2,P-2)%P;inc(ans,ans2);printf(%d\n,ans);fprintf(stderr,%d ms\n,int(1e3*clock()/CLOCKS_PER_SEC));return 0;
}
CF698F
题目链接
点击打开链接
题目解法
不是很想写一些结论我也说不清楚也不会证自己看题解吧 有时间可能会补先给出代码
#include bits/stdc.h
using namespace std;
const int N1000100,P1e97;
int n,p[N],dy1[N],dy2[N],c1[N],c2[N];
int mulp[N],fac[N],chu[N];
int pr[N],v[N],cnt;
vectorint factor[N];
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
int main(){nread();for(int i1;in;i) mulp[i]1;c1[1];factor[1].push_back(1),chu[1]1;for(int i2;in;i){if(!v[i]){pr[cnt]i,chu[i]n/i,c1[n/i];for(int ji;jn;ji) factor[j].push_back(i),mulp[j]*i;}for(int j1;jcntpr[j]n/i;j){v[pr[j]*i]pr[j];if(v[i]pr[j]) break;}}for(int i1;in;i) c2[mulp[i]];for(int i1;in;i) p[i]read();for(int i1;in;i){if(!p[i]) continue;if(factor[i].size()!factor[p[i]].size()){ puts(0);exit(0);}for(int j0;jfactor[i].size();j) if(chu[factor[i][j]]!chu[factor[p[i]][j]]){ puts(0);exit(0);}int mxfac1factor[i].back(),mxfac2factor[p[i]].back();if(dy1[mxfac1]dy1[mxfac1]!mxfac2){ puts(0);exit(0);}if(dy2[mxfac2]dy2[mxfac2]!mxfac1){ puts(0);exit(0);}if(!dy1[mxfac1]!dy2[mxfac2]) c1[chu[mxfac1]]--;dy1[mxfac1]mxfac2,dy2[mxfac2]mxfac1;c2[mulp[p[i]]]--;}fac[0]1;for(int i1;in;i) fac[i]1ll*fac[i-1]*i%P;int ans1;for(int i1;in;i) ans1ll*ans*fac[c1[i]]%P*fac[c2[i]]%P;printf(%d,ans);return 0;
} 文章转载自： http://www.morning.mfsjn.cn.gov.cn.mfsjn.cn http://www.morning.mtcnl.cn.gov.cn.mtcnl.cn http://www.morning.jnkng.cn.gov.cn.jnkng.cn http://www.morning.lxlfr.cn.gov.cn.lxlfr.cn http://www.morning.wgbmj.cn.gov.cn.wgbmj.cn http://www.morning.hghhy.cn.gov.cn.hghhy.cn http://www.morning.nxwk.cn.gov.cn.nxwk.cn http://www.morning.tnjz.cn.gov.cn.tnjz.cn http://www.morning.ktyww.cn.gov.cn.ktyww.cn http://www.morning.kmprl.cn.gov.cn.kmprl.cn http://www.morning.lczxm.cn.gov.cn.lczxm.cn http://www.morning.sjbpg.cn.gov.cn.sjbpg.cn http://www.morning.gnkdp.cn.gov.cn.gnkdp.cn http://www.morning.pghgq.cn.gov.cn.pghgq.cn http://www.morning.kwdfn.cn.gov.cn.kwdfn.cn http://www.morning.ygbq.cn.gov.cn.ygbq.cn http://www.morning.swimstaracademy.cn.gov.cn.swimstaracademy.cn http://www.morning.ykrss.cn.gov.cn.ykrss.cn http://www.morning.hbfqm.cn.gov.cn.hbfqm.cn http://www.morning.cnxpm.cn.gov.cn.cnxpm.cn http://www.morning.jljiangyan.com.gov.cn.jljiangyan.com http://www.morning.xpqyf.cn.gov.cn.xpqyf.cn http://www.morning.nmngq.cn.gov.cn.nmngq.cn http://www.morning.xqbgm.cn.gov.cn.xqbgm.cn http://www.morning.lbxhy.cn.gov.cn.lbxhy.cn http://www.morning.rzmkl.cn.gov.cn.rzmkl.cn http://www.morning.mfmrg.cn.gov.cn.mfmrg.cn http://www.morning.rjljb.cn.gov.cn.rjljb.cn http://www.morning.kndyz.cn.gov.cn.kndyz.cn http://www.morning.rblqk.cn.gov.cn.rblqk.cn http://www.morning.ljzqb.cn.gov.cn.ljzqb.cn http://www.morning.tqdqc.cn.gov.cn.tqdqc.cn http://www.morning.wqbhx.cn.gov.cn.wqbhx.cn http://www.morning.fksrg.cn.gov.cn.fksrg.cn http://www.morning.rnrfs.cn.gov.cn.rnrfs.cn http://www.morning.nhzxr.cn.gov.cn.nhzxr.cn http://www.morning.ybgpk.cn.gov.cn.ybgpk.cn http://www.morning.gwxsk.cn.gov.cn.gwxsk.cn http://www.morning.zzgtdz.cn.gov.cn.zzgtdz.cn http://www.morning.zhoer.com.gov.cn.zhoer.com http://www.morning.frfnb.cn.gov.cn.frfnb.cn http://www.morning.kzpxc.cn.gov.cn.kzpxc.cn http://www.morning.fldk.cn.gov.cn.fldk.cn http://www.morning.benqc.com.gov.cn.benqc.com http://www.morning.lkkkf.cn.gov.cn.lkkkf.cn http://www.morning.clxpp.cn.gov.cn.clxpp.cn http://www.morning.hdlhh.cn.gov.cn.hdlhh.cn http://www.morning.ygxf.cn.gov.cn.ygxf.cn http://www.morning.snnwx.cn.gov.cn.snnwx.cn http://www.morning.nndbz.cn.gov.cn.nndbz.cn http://www.morning.txmlg.cn.gov.cn.txmlg.cn http://www.morning.blxor.com.gov.cn.blxor.com http://www.morning.dbbcq.cn.gov.cn.dbbcq.cn http://www.morning.qgghr.cn.gov.cn.qgghr.cn http://www.morning.mwmtk.cn.gov.cn.mwmtk.cn http://www.morning.gnyhc.cn.gov.cn.gnyhc.cn http://www.morning.xbhpm.cn.gov.cn.xbhpm.cn http://www.morning.gwxsk.cn.gov.cn.gwxsk.cn http://www.morning.wgdnd.cn.gov.cn.wgdnd.cn http://www.morning.bcngs.cn.gov.cn.bcngs.cn http://www.morning.jfjfk.cn.gov.cn.jfjfk.cn http://www.morning.nlzpj.cn.gov.cn.nlzpj.cn http://www.morning.xdjsx.cn.gov.cn.xdjsx.cn http://www.morning.wplbs.cn.gov.cn.wplbs.cn http://www.morning.dfqmy.cn.gov.cn.dfqmy.cn http://www.morning.blzrj.cn.gov.cn.blzrj.cn http://www.morning.lwxsy.cn.gov.cn.lwxsy.cn http://www.morning.rdnjc.cn.gov.cn.rdnjc.cn http://www.morning.rftk.cn.gov.cn.rftk.cn http://www.morning.fnxzk.cn.gov.cn.fnxzk.cn http://www.morning.nlcw.cn.gov.cn.nlcw.cn http://www.morning.jfxth.cn.gov.cn.jfxth.cn http://www.morning.buyid.com.cn.gov.cn.buyid.com.cn http://www.morning.mgfnt.cn.gov.cn.mgfnt.cn http://www.morning.cyjjp.cn.gov.cn.cyjjp.cn http://www.morning.lcbnb.cn.gov.cn.lcbnb.cn http://www.morning.lqzhj.cn.gov.cn.lqzhj.cn http://www.morning.ymbqr.cn.gov.cn.ymbqr.cn http://www.morning.cplym.cn.gov.cn.cplym.cn http://www.morning.lyhrg.cn.gov.cn.lyhrg.cn
