测试赛 - ljc20020730 解题报告
标签（空格分隔）： solution
Task A Tiat's easy question
首先，判断图中是否存在长度为奇数的环等价于判断图是否为二分图。
这个两个事情互为充分必要条件。
只需要染色即可，图可能不连通。
复杂度(O(n))
# include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=2e6+10;
struct rec{
int pre,to;
}a[M<<1];
int n,m,tot,head[N],col[N];
void adde(int u,int v)
{
a[++tot].pre=head[u];
a[tot].to=v;
head[u]=tot;
}
void dfs(int u,int c)
{
col[u]=c;
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to; int sd=(c==1)?2:1;
if (col[v]==col[u]) { puts("N"); exit(0);}
if (!col[v]) dfs(v,sd);
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++) {
int u,v; scanf("%d%d",&u,&v);
adde(u,v); adde(v,u);
}
for (int i=1;i<=n;i++) if (!col[i]) dfs(i,1);
puts("Y");
return 0;
}
Task B Nephren's last plan
我们观察到，完全平方数完全是可以取或者不取的，可以统一起来考虑。
不妨设完全平方数的个数为(ret_1)个.
而对于其他非完全平方数，我们可以对其进行完全分解。
设(a_i)完全分解中某一项为(p_i ^ {k_i}) 其中$p_i in Prime $
-
若(k_i equiv 0 (mod 2)) , 则 该元素对 质数 (p_i) 没有意义。
-
若(k_i equiv 1 (mod 2)) , 则 该元素对 质数 (p_i) 有意义。
由于最终必须是连乘使得最终答案是完全平方数，这等价于对每个素数有贡献的元素中只能选择偶数个。 对不同素数有贡献的元素之间又存在连带关系。
所以，对于每一个素数都可以对应一个异或方程组，我们可以将其写成矩阵的形式。
定义矩阵(A_{i,j})表示下列方程组的解 ((x_1 , ... , x_n))
$A_{1,1} imes x_1 igoplus A_{1,2} imes x_2 igoplus...igoplus A_{1,n} imes x_n = 0 ( )A_{2,1} imes x_1 igoplus A_{2,2} imes x_2 igoplus...igoplus A_{2,n} imes x_n = 0 ( ) ......( )A_{n,1} imes x_1 igoplus A_{n,2} imes x_2 igoplus...igoplus A_{n,n} imes x_n = 0 $
可以高斯消元求出矩阵的秩 ， 然后求出自由元个数(ret_2)。
最终的答案$ ans $一定是(2^{ret_1+ret_2} equiv ans (mod 998244353))
注意到值相同的不同元素应该算为不同的元。
# include<bits/stdc++.h>
# define int long long
using namespace std;
bool ok[505],is_pr[505];
int n,cnt,ret1,ret2,num;
int a[1005],t[505][505],pr[505],mark[505];
vector<int>p[505];
void EouLaShai(int Lim)
{
memset(is_pr,true,sizeof(is_pr));
is_pr[1]=false;
for (int i=2;i<=Lim;i++) {
if (is_pr[i]) pr[++pr[0]]=i,mark[i]=i;
for (int j=1;j<=pr[0]&&i*pr[j]<=Lim;j++) {
mark[i*pr[j]]=pr[j];
is_pr[i*pr[j]]=false;
if (i%pr[j]==0) break;
}
}
}
void work(int x)
{
++num; bool flag=false;
while (x!=1) {
int y=mark[x],z=0;
while (x%y==0) x/=y,z++;
if (z&1) p[y].push_back(num),flag=true;
}
if (!flag) --num;
}
int gauss()
{
int i,j,k,x,y;
for (i=1,j=1;i<=cnt&&j<=num;j++) {
k=i; while (k<=cnt&&!t[k][j]) ++k;
if (t[k][j]) {
swap(t[i],t[k]);
for (x=i+1;x<=cnt;x++) if (t[x][j])
for (y=i;y<=num;y++) t[x][y]^=t[i][y];
i++;
}
}
return num-i+1;
}
int Pow(int x,int n,int p)
{
int ans=1;
while (n) {
if (n&1) ans=ans*x%p;
x=x*x%p; n>>=1;
}
return ans%p;
}
signed main()
{
EouLaShai(500); scanf("%lld",&n);
for (int i=1;i<=n;i++) {
int t; scanf("%lld",&t);
if (((int)sqrt(t))*((int)sqrt(t))==t) { ret1++; continue;}
a[++a[0]]=t;
}
for (int i=1;i<=a[0];i++) work(a[i]);
for (int i=1;i<=500;i++) if (is_pr[i] && p[i].size()) {
++cnt;
for (int j=0;j<p[i].size();j++) t[cnt][p[i][j]]=1;
}
int ret2=gauss();
printf("%lld
",Pow(2,ret1+ret2,998244353));
return 0;
}
Task C Tiat and random
首先，黑点=白点的情况对答案没有贡献，可以不用考虑。
设染黑点数目少于白点数目，显然另外一半情况与该情况完全相同。
设染黑点数目是(i)，为了满足上述限制，(i in [0,lfloorfrac{k}{2} floor ])
那么选取的方法是(inom{k}{i})种，总贡献是(inom{k}{i}(k-2i))
所以这道题最终答案就是(frac{2 sumlimits _{i=0} ^{lfloorfrac{k}{2} floor}inom{k}{i}(k-2i)}{2^k})
即 ((2^{-1})^{k-1} sumlimits _{i=0} ^{lfloorfrac{k}{2} floor}inom{k}{i}(k-2i) mod 2000003)
由于有(n)组询问，这样计算时间复杂度是(O(nk))，
我们考虑转化一下这个式子。
我们关心 $sumlimits _{i=0} ^{lfloorfrac{k}{2} floor}inom{k}{i}(k-2i) $ 这一部分。
原式可化为 ： (k sumlimits_{i=0}^{lfloorfrac{k}{2} floor}inom{k}{i} - 2sumlimits_{i=0}^{lfloorfrac{k}{2} floor} iinom{k}{i})
显然若(k = 2k')或(k=2k'+1,k'in Z)，需要讨论。
观察(sumlimits_{i=0}^{lfloorfrac{k}{2} floor}inom{k}{i}) 我们可以归纳得出，
- 当(k=2k')时，值就是$2^{k-1} + frac{1}{2} inom{k}{k'} $
- 当(k=2k'+1)时，值就是(2^{k-1}).
观察(sumlimits_{i=0}^{lfloorfrac{k}{2} floor} iinom{k}{i} = sumlimits_{i=1}^{lfloorfrac{k}{2} floor} iinom{k}{i}),而可以证明：$iinom{k}{i} = k inom{k-1}{i-1} $
这里证明一下结论 (iinom{k}{i} = k inom{k-1}{i-1}) : $iinom{k}{i} =frac{i imes k!}{(k-i)!i!} = frac{k imes(k-1)!}{(k-i)!(i-1)!} = kinom{k-1}{i-1} $
(sumlimits_{i=0}^{lfloorfrac{k}{2} floor} iinom{k}{i})可化为(k sumlimits_{i=1}^{lfloorfrac{k}{2} floor} inom{k-1}{i-1} = k sumlimits_{i=0}^{lfloorfrac{k}{2} floor -1} inom{k-1}{i})
我们可以归纳得出：
- 当(k=2k')时，答案就是(2^{k-2}k),
- 当(k=2k'+1)时，答案就是(frac{2^{k-1}-inom{k-1}{k'}}{2} k).
由于真正的答案 $ Ans = (2^{-1})^{k-1} (k sumlimits_{i=0}^{lfloorfrac{k}{2} floor}inom{k}{i} - 2sumlimits_{i=0}^{lfloorfrac{k}{2} floor} iinom{k}{i})$
- 若当(k=2k')时，
(Ans = (2^{-1})^{k-1} imes (k(2^{k-1} + frac{1}{2} inom{k}{k'})-2(k imes 2^{k-2})))
(= (2^{-1})^k k inom{k}{k'} = 2k'inom{2k'}{k'}(2^{-1})^{2k'}) - 若当(k=2k'+1)时，
$Ans = (2^{-1})^{k-1} imes (k(2^{k-1})-2 imes frac{2^{k-1}-inom{k-1}{k'}}{2} k ) ( )= inom{k-1}{k'} k (2^{-1}) ^{k-1} =(2k'+1) inom{2k'-1}{k'} (2^{-1}) ^{2k'-1}$
综上所述，(当(k)为奇数且为1时，组合数会取到负数，我们可以特判处理)
(Ans(1) = frac{|1-0|+|0-1|}{2^1} = 1.)
(Ans(2k') = 2k'inom{2k'}{k'}(2^{-1})^{2k'} , k' in N).
(Ans(2k'+1) = (2k'+1) inom{2k'-1}{k'} (2^{-1}) ^{2k'-1},k'in N^+).
实现方面，可以预处理逆元、阶乘前缀积、阶乘逆元前缀积、2的逆元幂次等然后通过lucas定理求出组合数取模，然后由于模数不是非常小，所以询问基本上是(O(1))的。
总复杂度： (O(n))
# include<bits/stdc++.h>
# define int long long
using namespace std;
const int N=2e6+1000;
const int mo=2000003;
int s[N],inv[N],Pow[N];
int n,m;
void init(int len)
{
s[0]=inv[0]=inv[1]=1;
for (int i=1;i<=len;i++) s[i]=s[i-1]*i%mo;
for (int i=2;i<=len;i++) inv[i]=(mo-mo/i)%mo*inv[mo%i]%mo;
for (int i=2;i<=len;i++) inv[i]=inv[i-1]*inv[i]%mo;
Pow[0]=1; for (int i=1;i<=len;i++) Pow[i]=Pow[i-1]*inv[2]%mo;
}
int lucas(int n,int m)
{
if (m>n) return 0;
if (n<mo&&m<mo) return s[n]*inv[n-m]%mo*inv[m]%mo;
return lucas(n%mo,m%mo)*lucas(n/mo,m/mo)%mo;
}
signed main(){
init(2e6+100);
int n; scanf("%lld",&n);
while (n--) {
int k; scanf("%lld",&k);
if (k==1) { puts("1");continue;}
if (k&1) {
k/=2; int ans=(2*k+1)*Pow[2*k-1]%mo*lucas(2*k-1,k)%mo;
printf("%lld
",ans);
} else {
k/=2; int ans=(2*k)*Pow[2*k]%mo*lucas(2*k,k)%mo;
printf("%lld
",ans);
}
}
return 0;
}