首页 > 代码库 > 【CF832E】Vasya and Shifts 高斯消元
【CF832E】Vasya and Shifts 高斯消元
【CF832E】Vasya and Shifts
题意：给你n个5进制数a1,a2...an，每个数都有4个，有m个询问，每次给你一个数bi，要你用a中的数进行不进位的加法来得到bi，求方案数。
题解：先考虑一个询问，我们设未知数xi表示第i个数用了几个，那么可以列出方程组。如果方程组无解，那么答案为0；否则答案就是5^(自由元的个数)。
多组询问呢？直接将全部询问构成的矩阵扔到系数矩阵的右面然后消元就行了。
#include <cstdio>#include <cstring>#include <iostream>using namespace std;int n,m,q,cnt;long long ans;char str[510];int v[510][1010],imp[510];int ine(int x){ return x*x*x%5;}int main(){ scanf("%d%d",&n,&m); int i,j,k,now; for(i=1;i<=n;i++) { scanf("%s",str+1); for(j=1;j<=m;j++) v[j][i]=str[j]-‘a‘; } scanf("%d",&q); for(i=1;i<=q;i++) { scanf("%s",str+1); for(j=1;j<=m;j++) v[j][n+i]=str[j]-‘a‘; } for(now=i=1;i<=m&&now<=n;i++,now++) { for(j=i+1;j<=m;j++) if(v[j][now]>v[i][now]) for(k=now;k<=n+q;k++) swap(v[j][k],v[i][k]); while(!v[i][now]&&now<=n) now++,cnt++; if(now>n) break; int t=ine(v[i][now]); for(k=now;k<=n+q;k++) v[i][k]=v[i][k]*t%5; for(j=i+1;j<=m;j++) if(v[j][now]) { t=v[j][now]; for(k=now;k<=n+q;k++) v[j][k]=((v[j][k]-t*v[i][k])%5+5)%5; } } if(now<=n) cnt+=n-now+1; for(;i<=m;i++) for(k=n+1;k<=n+q;k++) if(v[i][k]) imp[k-n]=1; for(ans=1,i=1;i<=cnt;i++) ans=ans*5%1000000007; for(i=1;i<=q;i++) printf("%I64d\n",imp[i]?0ll:ans); return 0;}//2 1 c b 1 a
【CF832E】Vasya and Shifts 高斯消元
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。