【题解】牛客挑战赛53
视频题解
A、智乃哥哥的小迷题A
如果我们最小可以取的答案为 。
那么必然满足如下条件：
假如我们已经知道了 那么答案可能为
我们计 显然有
那么如果 那么答案就是前
个数每个数都加
的移动方式，那么答案为
如果 那么答案还是
。
因为对于 我们应该要满足
因为如果不满足就需要
。
然后我们可以把第 次操作的移动方式从加
变成
. 那么这个柿子答案为
。
如果 
那么无法通过替换数来达到 
那么需要多加一次操作去 
.
#include <bits/stdc++.h>
using namespace std;
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
#define int long long
#define Rep(x, a, b) for(int x = a; x <= b; ++ x)
#define Dep(x, a, b) for(int x = a; x >= b; -- x)
#define Next(i, x) for(int i = head[x]; i ; i = e[i].nxt)
int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
const int maxn = 1e6;
const int inf = 1e9;
signed main() {
int T = read();
while(T --) {
int x = read(), num = 0, now = (int) ceil(((double) -1.0 + sqrt(1.0 + 8.0 * ((double) x))) * 0.5);
num = (now + 1) * now / 2;
if(num - x == 1) printf("%lld\n", now + 1); else printf("%lld\n", now);
}
return 0;
} B、简单的序列
肯定有很多人写贪心吧，可能没有（
首先我们发现如果 是一个偶数，那么他必然可以分解成
个质数之和，由哥德巴赫猜想可知。
然后奇数的话有 种可能性，一种是他可以由
和另一个质数相加，这种只是
是不是质数即可。
另一种是把奇数分成偶数 然后对于偶数再求之前的东西。
然后这个东西每次求解只要枚举质数就行了，
以内质数只有 
个大概可以草过去。
#include <bits/stdc++.h>
using namespace std;
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
#define int long long
#define Rep(x, a, b) for(int x = a; x <= b; ++ x)
#define Dep(x, a, b) for(int x = a; x >= b; -- x)
#define Next(i, x) for(int i = head[x]; i ; i = e[i].nxt)
int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
const int maxn = 1e7 + 10;
const int maxm = 2010;
const int XRZ = 1e9 + 7;
int vis[maxn], pri[maxn], cnt;
void init(int x) { pri[1] = 1;
Rep(i, 2, x) {
if(! vis[i]) pri[++ cnt] = i;
for(int j = 1; j <= cnt && i * pri[j] <= x; ++ j) {
vis[i * pri[j]] = 1;
if(i % pri[j] == 0) break;
}
}
}
signed main() {
// freopen("a10.in", "r", stdin);
// freopen("a10.out", "w", stdout);
int T = read();
init(1e7);
while(T --) {
int n = read(), l = 1, r = cnt;
if(! vis[n]) { printf("1\n%d = %d\n", n, n); continue ;}
if(n % 2) {
if(! vis[n - 2]) {
printf("2\n2 + %d = %d\n", n - 2, n);
continue ;
} else { puts("3");
Rep(i, 1, cnt) {
if(! vis[n - 1 - pri[i]]) {
printf("1 + %d + %d = %d\n", pri[i], n - 1 - pri[i], n);
break ;
}
}
}
} else { puts("2");
Rep(i, 1, cnt) {
if(! vis[n - pri[i]]) {
printf("%d + %d = %d\n", pri[i], n - pri[i], n);
break ;
}
}
}
}
return 0;
} C、奇奇怪怪的魔法阵
考虑状压dp，设)表示
)的子集内独立集的个数。考虑转移，在
)中随便选一个元素
)。考虑
)在不在独立集里，如果不在的话，
)号点对其它点是没有影响的，直接从
)转移。如果在的话，
)号点的所有邻居都不能在独立集里，设
)号点及其邻居的节点集合为
)，这种情况就从
转移即可。
时间复杂度&preview=true)
。
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,x,y,msk[55],dp[(1<<26)+10],fun[(1<<25)+10],id,ans;
int main()
{
scanf("%d%d",&n,&m);
for (int i=0;i<n;i++) msk[i]=1<<i;
for (int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
msk[x]|=(1<<y);
msk[y]|=(1<<x);
}
for (int i=0;i<n;i++) fun[1<<i]=i;
dp[0]=1;
for (int i=1;i<(1<<n);i++)
{
id=fun[i&(-i)];
dp[i]=dp[i^(1<<id)]+dp[i^(i&msk[id])];
if (dp[i]>=mod) dp[i]-=mod;
}
for (int i=(1<<n)-1;i>=0;i--) ans=(233ll*ans+dp[i])%mod;
printf("%d\n",ans);
return 0;
} D、离线版OEIS
Tag：高斯消元，线性递推
这个题看样例就劝退...其实，我觉得还挺简单的，至少比H简单。
首先这个题就是求一个线性式加一个常数多项式的形式。首先考虑拆成两个部分，也就是线性式和多项式部分。（实际上多项式可以线性递推）。
如果一个递推式中的某项能用它之前的k项表示，我们就称它是一个k阶多项式，显然，线性式有一阶线性递推，二阶线性递推...
对于多项式，如果它的最高次项是k次，我们就称它是一个k次多项式。
因为这道题多项式的阶数最多是3，递推式的阶数最多是5。所以可以两重循环枚举，先固定递推式和多项式阶数。
固定以后其实这个式子的结构就定了，我们举个简单的例子，比如输入的数据是斐波那契数列
1 1 2 3 5 8 13 21....
然后加入你枚举到“二阶递推式+一阶多项式”，也就是说你猜测这个式子的结构可能是这样的。
然后因为输入的数据就是连续的项，所以我们可以选择比如1-3项填进去，2-4项填进去，等等。
然后就可以列出一个方程组，比如这里就是分别取1-3,2-4,3-5,4-6项填入。
时间复杂度%5E%7B3%7D)&preview=true)
，其中n为递推式阶数上限，m为多项式阶数上限。
#include<bits/stdc++.h>
#define N 205
using namespace std;
const double eps=1e-8;
int number;
int T,ans;
double a[N][N],del;
long long arr[N],ki[30];
bool flag;
bool gauss(int n)
{
for(int i=1;i<=n;i++)
{
int k=i;
for(int j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[k][i]))k=j;
if(fabs(del=a[k][i])<eps)return 0;
for(int j=i;j<=n+1;j++)swap(a[i][j],a[k][j]);
for(int j=i;j<=n+1;j++)a[i][j]/=del;
for(k=1;k<=n;k++)if(k!=i)
{
del=a[k][i];
for(int j=i;j<=n+1;j++)a[k][j]-=a[i][j]*del;
}
}
return 1;
}
void work(long long k)
{
memset(a,0,sizeof(a));
for(long long i=1;i<=k+4;++i)
{
for(long long j=1;j<=k;++j)
{
a[i][j]=arr[i+j-1];
}
a[i][k+1]=1;
a[i][k+2]=(i+k);
a[i][k+3]=(i+k)*(i+k);
a[i][k+4]=(i+k)*(i+k)*(i+k);
a[i][k+5]=arr[i+k];
}
if(gauss(k+4))
{
memset(ki,0,sizeof(ki));
for(int i=1;i<=k+4;++i)
{
ki[i]=round(a[i][k+5]);
}
for(int i=1;i<=k/2;++i)
{
swap(ki[i],ki[k-i+1]);
}
for(long long i=k+1;i<=number;++i)
{
long long sum=0;
for(int j=1;j<=k;++j)
{
sum+=arr[i-j]*ki[j];
}
sum+=ki[k+1];
sum+=ki[k+2]*i;
sum+=ki[k+3]*i*i;
sum+=ki[k+4]*i*i*i;
if(arr[i]!=sum)return;
}
flag=true;
return;
}
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&number);
for(int i=1;i<=number;++i)
{
scanf("%lld",&arr[i]);
}
flag=false;
for(int i=0;i<=5;++i)
{
work(i);
if(flag)
{
ans=i;
break;
}
}
if(flag)
{
if(ans)
{
printf("a[1]=%d",arr[1]);
}
for(int i=2;i<=ans;++i)
{
printf(",a[%d]=%d",i,arr[i]);
}
if(ans)printf("\n");
printf("a[i]=");
bool fi=true;
for(int i=1;i<=ans;++i)
{
if(ki[i])
{
if(ki[i]>0)
{
if(!fi)printf("+");
}
else
{
printf("-");
}
if(abs(ki[i])!=1)
{
printf("%lld*a[i-%d]",abs(ki[i]),i);
}
else
{
printf("a[i-%d]",i);
}
fi=false;
}
}
if(ki[ans+4])
{
if(ki[ans+4]>0)
{
if(!fi)printf("+");
}
else
{
printf("-");
}
if(abs(ki[ans+4])!=1)
{
printf("%lld*i*i*i",abs(ki[ans+4]));
}
else
{
printf("i*i*i");
}
fi=false;
}
if(ki[ans+3])
{
if(ki[ans+3]>0)
{
if(!fi)printf("+");
}
else
{
printf("-");
}
if(abs(ki[ans+3])!=1)
{
printf("%lld*i*i",abs(ki[ans+3]));
}
else
{
printf("i*i");
}
fi=false;
}
if(ki[ans+2])
{
if(ki[ans+2]>0)
{
if(!fi)printf("+");
}
else
{
printf("-");
}
if(abs(ki[ans+2])!=1)
{
printf("%lld*i",abs(ki[ans+2]));
}
else
{
printf("i");
}
fi=false;
}
if(ki[ans+1])
{
if(ki[ans+1]>0)
{
if(!fi)printf("+");
}
else
{
printf("-");
}
printf("%lld",abs(ki[ans+1]));
fi=false;
}
if(fi)printf("0");
printf("\n");
}
else
{
printf("No_solution\n");
}
}
return 0;
}
/*
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n+1;j++)scanf("%lf",&a[i][j]);
bool flag=gauss();
if(!flag)puts("No Solution");
else for(int i=1;i<=n;i++)printf("%.2lf\n",a[i][n+1]);
*/ E、F拱桥
Tag：构造，带花树（一般图匹配）
这个题的灵感是CF上面有一个问国际象棋棋盘上面最多可以放置多少组能够互相攻击的马，然后我这个题相当于增强了一下。
首先先看easy version，注意到棋盘的格子很少，属于经典的棋盘上的匹配问题。对于这种问题，建图的时候可以用一个国际象棋的棋盘（黑白格）看一眼是不是二分图，显然这个题不是个二分图，那它就是个一般图匹配。
所以直接掏个带花树一般图匹配的板子就行了。
建图就是每个点和它欧几里得距离[1.5,2.5]之间的点连边，其实就是如下图所示的连边方式。然后建边的时候注意一下坏格就行了。
PS比赛过程中有人问了这么个问题。。。
草，仔细一想这桥穿模了啊。
然后hard的话其实就是用了这种“穿模”的构造方式，首先可以组成一个1*4大小的结构，就1 2 1 2这样造就可以了。
然后因为有easy版本的算法，也就是说当图很小的时候，你只需要跑一个一般图匹配就行了。
具体来讲，你要这样，因为可以做)的构造，所以其实任意的
就都可以构造出来，假设星星部分是坏点，就可以这样构造。
但是如果你这么想当然的直接写，那就又WA了。
注意这种情况，你不能够把坏点逼到角落，这样会使得做匹配的时候无法调整，所以一个比较好的方式是上下左右各留出至少6个格子的余地，然后剩下的交给一般图匹配。
时间复杂度%5E3)&preview=true)
其中N,M为原本图的大小，n,m为构造后剩余带坏点的部分大小。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=505;
const int MAXM=MAXN*MAXN*2;
const int MAXSIZE=1000005*4;
int n,m,que[MAXM],head,tail,pre[MAXN],tim,g[MAXN],tot,match[MAXN],fa[MAXN],type[MAXN],tic[MAXN],r,c;
int ans[MAXN];
int u[MAXN],v[MAXN];
int dx[]={-2,-1,0,1,2,2};
int dy[]={1,2,2,2,1,0};
int U,D,L,R,N,M;
int px,py,x,y,T;
int mp[MAXSIZE];
struct edge
{
int to,next;
}e[MAXM];
int findf(int x)
{
return fa[x]==x?fa[x]:fa[x]=findf(fa[x]);
}
void add_edge(int from,int to)
{
e[++tot].to=to;
e[tot].next=g[from];
g[from]=tot;
}
void init()
{
tim=0;
tot=0;
for(int i=0;i<=n;++i)
{
g[i]=0;
match[i]=0;
tic[i]=0;
ans[i]=0;
}
}
int lca(int x,int y)
{
++tim;
while(1)
{
if(x)
{
x=findf(x);
if(tic[x]==tim)
{
return x;
}
else
{
tic[x]=tim;
x=pre[match[x]];
}
}
swap(x,y);
}
}
void shrink(int x,int y,int p)
{
while (findf(x)!=p)
{
pre[x]=y,y=match[x];
if (type[y]==2) type[y]=1,que[++tail]=y;
if (findf(x)==x) fa[x]=p;
if (findf(y)==y) fa[y]=p;
x=pre[y];
}
}
bool aug(int s)
{
for(int i=1;i<=n;++i)
{
fa[i]=i;
type[i]=0;
pre[i]=0;
}
head=0;
tail=1;
que[tail]=s;
type[s]=1; // 1: type A ; 2: type B
int t=0;
while (head<tail)
{
int x=que[++head];
for (int i=g[x];i;i=e[i].next)
{
if (findf(e[i].to)==findf(x)||type[e[i].to]==2) continue;
if (!type[e[i].to])
{
type[e[i].to]=2,pre[e[i].to]=x;
if (!match[e[i].to])
{
int last,tmp;
for (int now=e[i].to;now;now=last)
{
tmp=pre[now];
last=match[tmp];
match[now]=tmp;
match[tmp]=now;
}
return true;
}
type[match[e[i].to]]=1;
que[++tail]=match[e[i].to];
}
else if (type[e[i].to]==1)
{
int l=lca(x,e[i].to);
shrink(x,e[i].to,l);
shrink(e[i].to,x,l);
}
}
}
return false;
}
int EMA()
{
int ans=0;
for(int i=1;i<=n;++i)
{
ans+=(!match[i]&&aug(i));
}
return ans;
}
int ha(int x,int y)
{
return (x-1)*c+y;
}
int mha(int x,int y)
{
return (x-1)*M+y;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&N,&M);
scanf("%d %d",&px,&py);
U=L=1,D=N,R=M;
while(py-L>8)L+=4;
while(px-U>8)U+=4;
while(R-py>8)R-=4;
while(D-px>8)D-=4;
x=px-U+1;
y=py-L+1;
r=D-U+1;
c=R-L+1;
n=r*c;
init();
for(int i=0;i<=N*M;++i)
{
mp[i]=0;
}
for(int i=1;i<=r;++i)
{
for(int j=1;j<=c;++j)
{
for(int k=0;k<6;++k)
{
int nowx=i+dx[k];
int nowy=j+dy[k];
if(i==x&&j==y)continue;
if(nowx==x&&nowy==y)continue;
if(nowx>=1&&nowx<=r&&nowy>=1&&nowy<=c)
{
add_edge(ha(i,j),ha(nowx,nowy));
add_edge(ha(nowx,nowy),ha(i,j));
}
}
}
}
EMA();
int cnt=0;
for(int i=1;i<=r;++i)
{
for(int j=1;j<=c;++j)
{
if(ans[ha(i,j)])continue;
if(match[ha(i,j)])
{
ans[ha(i,j)]=ans[match[ha(i,j)]]=++cnt;
}
}
}
for(int i=1;i<=r;++i)
{
for(int j=1;j<=c;++j)
{
mp[mha(U+i-1,L+j-1)]=ans[ha(i,j)];
}
}
for(int j=1;j<L;j+=4)
{
for(int i=1;i<=N;++i)
{
mp[mha(i,j)]=mp[mha(i,j+2)]=++cnt;
mp[mha(i,j+1)]=mp[mha(i,j+3)]=++cnt;
}
}
for(int j=M;j>R;j-=4)
{
for(int i=1;i<=N;++i)
{
mp[mha(i,j)]=mp[mha(i,j-2)]=++cnt;
mp[mha(i,j-1)]=mp[mha(i,j-3)]=++cnt;
}
}
for(int i=1;i<U;i+=4)
{
for(int j=L;j<=R;++j)
{
mp[mha(i,j)]=mp[mha(i+2,j)]=++cnt;
mp[mha(i+1,j)]=mp[mha(i+3,j)]=++cnt;
}
}
for(int i=N;i>D;i-=4)
{
for(int j=L;j<=R;++j)
{
mp[mha(i,j)]=mp[mha(i-2,j)]=++cnt;
mp[mha(i-1,j)]=mp[mha(i-3,j)]=++cnt;
}
}
for(int i=1;i<=N;++i)
{
for(int j=1;j<=M;++j)
{
printf("%d%c",mp[mha(i,j)]?mp[mha(i,j)]:-1,j==M?'\n':' ');
}
}
}
return 0;
} G、H同源数组
Tag：MTT/NTT，卢卡斯定理，同余方程/乘法逆元。
首先你要知道，对于某个数组求一次前缀和，它等价与和全1数组做一次卷积。
然后有个性质，叫做当模是大质数)的时候，一个数组做
次前缀和相当于没有做前缀和。
然后你可能要学一点多项式，前置只是我放在这里了
其实你只用看那个快速k阶前缀和的卷积式就可以了。
根据快速前缀和的卷积式，k次前缀和一个组合数的贡献。（其实从这里能看出来，这个题的本质是求一个逆组合数问题）
但是如果是大模数的话，根本不用想那么多，其实就看前两项就行了。
一个数组a,对它做k次前缀和后，它的前两项用原本的数组表示就是 。
然后昨晚了easy，可能大部分人都觉得这不直接上个多项式板子就能直接做hard，但是...。实际上就WA了。
你发现这个算法在小模的时候不适用。
为什么呢，是因为有个叫做卢卡斯定理的东西在捣乱。回到这个问题一开始的地方，求一个数组到另一个数组是做了几次前缀和，本质是一个逆组合数问题，但是谁告诉你求出来的这个k它就是唯一的了。然后这个时候你就看卢卡斯定理的式子，然后对于这个式子有一种理解是它是有点像进制转换一样，递归的往下除一次模一次。
所以现在要做的，其实就是一个“逆卢卡斯定理”，其实方法也很简单，比如模数是7，那么只要用easy中的方法以此对其第1,7,49,343...,然后对不同的数组进行分组，也就是不停地按照处理对数组进行分组，直到其大于数组长度为止即可。
时间复杂度&preview=true)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2077;
int mod;
namespace Math {
inline int pw(int base, int p, const int mod) {
static int res;
for (res = 1; p; p >>= 1, base = static_cast<long long> (base) * base % mod) if (p & 1) res = static_cast<long long> (res) * base % mod;
return res;
}
inline int inv(int x, const int mod) { return pw(x, mod - 2, mod); }
}
const int mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3;
const long long mod_1_2 = static_cast<long long> (mod1) * mod2;
const int inv_1 = Math::inv(mod1, mod2), inv_2 = Math::inv(mod_1_2 % mod3, mod3);
struct Int {
int A, B, C;
explicit inline Int() { }
explicit inline Int(int __num) : A(__num), B(__num), C(__num) { }
explicit inline Int(int __A, int __B, int __C) : A(__A), B(__B), C(__C) { }
static inline Int reduce(const Int &x) {
return Int(x.A + (x.A >> 31 & mod1), x.B + (x.B >> 31 & mod2), x.C + (x.C >> 31 & mod3));
}
inline friend Int operator + (const Int &lhs, const Int &rhs) {
return reduce(Int(lhs.A + rhs.A - mod1, lhs.B + rhs.B - mod2, lhs.C + rhs.C - mod3));
}
inline friend Int operator - (const Int &lhs, const Int &rhs) {
return reduce(Int(lhs.A - rhs.A, lhs.B - rhs.B, lhs.C - rhs.C));
}
inline friend Int operator * (const Int &lhs, const Int &rhs) {
return Int(static_cast<long long> (lhs.A) * rhs.A % mod1, static_cast<long long> (lhs.B) * rhs.B % mod2, static_cast<long long> (lhs.C) * rhs.C % mod3);
}
inline int get() {
long long x = static_cast<long long> (B - A + mod2) % mod2 * inv_1 % mod2 * mod1 + A;
return (static_cast<long long> (C - x % mod3 + mod3) % mod3 * inv_2 % mod3 * (mod_1_2 % mod) % mod + x) % mod;
}
} ;
#define maxn 131072
namespace Poly {
#define N (maxn << 1)
int lim, s, rev[N];
Int Wn[N | 1];
inline void init(int n) {
s = -1, lim = 1; while (lim < n) lim <<= 1, ++s;
for (int i = 1; i < lim; ++i) rev[i] = rev[i >> 1] >> 1 | (i & 1) << s;
const Int t(Math::pw(G, (mod1 - 1) / lim, mod1), Math::pw(G, (mod2 - 1) / lim, mod2), Math::pw(G, (mod3 - 1) / lim, mod3));
*Wn = Int(1); for (Int *i = Wn; i != Wn + lim; ++i) *(i + 1) = *i * t;
}
inline void NTT(Int *A, const int op = 1) {
for (int i = 1; i < lim; ++i) if (i < rev[i]) std::swap(A[i], A[rev[i]]);
for (int mid = 1; mid < lim; mid <<= 1) {
const int t = lim / mid >> 1;
for (int i = 0; i < lim; i += mid << 1) {
for (int j = 0; j < mid; ++j) {
const Int W = op ? Wn[t * j] : Wn[lim - t * j];
const Int X = A[i + j], Y = A[i + j + mid] * W;
A[i + j] = X + Y, A[i + j + mid] = X - Y;
}
}
}
if (!op) {
const Int ilim(Math::inv(lim, mod1), Math::inv(lim, mod2), Math::inv(lim, mod3));
for (Int *i = A; i != A + lim; ++i) *i = (*i) * ilim;
}
}
#undef N
}
const int MAXSZ=1000005;
int ki[MAXN];
Int Ki[MAXN];
long long fac[MAXSZ],invfac[MAXSZ],inv[MAXSZ];
void init(int n)
{
invfac[0]=1;
fac[0]=1;
inv[1]=1;
for(int i=2;i<=n;++i) inv[i]=((mod-mod/i)*inv[mod%i])%mod;
for(int i=1;i<=n;++i) fac[i]=fac[i-1]*i%mod,invfac[i]=invfac[i-1]*inv[i]%mod;
}
long long C(long long n,long long m)
{
return fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
long long lucas(long long n,long long m)
{
return m==0?1:lucas(n/mod,m/mod)*C(n%mod,m%mod)%mod;
}
void getKi(long long k,int len)
{
memset(Ki,0,sizeof(Ki));
if(mod>=1e6)
{
ki[0]=1;
for(int i=1;i<len;++i)
{
ki[i]=ki[i-1]*inv[i]%mod*((k+i-1)%mod)%mod;
}
}
else
{
for(int i=0;i<len;++i)
{
ki[i]=lucas(k+i-1,i);
}
}
for(int i=0;i<len;++i)
{
Ki[i]=Int(ki[i]);
}
}
int n,m,id[MAXN],prezero[MAXN],temp[MAXN][MAXN],x;
bool isTop[MAXN];
Int a[MAXN][MAXN];
void debugger(string note="")
{
cout<<"---------------debugger---------------"<<endl;
if(note!="")cout<<note<<endl;
int group=0;
for(int i=0;i<n;++i)
{
if(isTop[id[i]])
{
++group;
cout<<"------------ group "<<group<<" ------------"<<endl;
}
printf("%4d :",id[i]);
for(int j=0;j<m;++j)
{
cout<<a[id[i]][j].get()<<" ";
}
cout<<endl;
}
cout<<" total group : "<<group<<endl;
}
void GroupByPreZero()
{
for(int l=0,r=0;l<n;l=++r)
{
while(r<n-1&&!isTop[r+1])++r;
sort(id+l,id+r+1,[](const int &ID__A,const int &ID__B){
return prezero[ID__A]<prezero[ID__B];
});
for(int i=l;i<=r;++i)
{
isTop[id[i]]=(i==l||prezero[id[i]]!=prezero[id[i-1]]);
}
}
return;
}
void GroupByLexicographicalOrder(long long len)
{
for(int l=0,r=0;l<n;l=++r)
{
while(r<n-1&&!isTop[id[r+1]])++r;
int delta=prezero[id[l]];
for(int i=l;i<=r;++i)
{
for(int j=0;j<m;++j)
{
temp[id[i]][j]=a[id[i]][j].get();
}
}
sort(id+l,id+r+1,[](const int &ID__A,const int &ID__B){
int pin=0;
while(pin<m-1&&temp[ID__A][pin]==temp[ID__B][pin])++pin;
return temp[ID__A][pin]<temp[ID__B][pin];
});
for(int i=l;i<=r;++i)
{
if(i==l)
{
isTop[id[i]]=true;
}
else
{
int pin=delta;
while(pin<min(delta+len,(long long)m)-1&&temp[id[i-1]][pin]==temp[id[i]][pin])++pin;
if(temp[id[i-1]][pin]!=temp[id[i]][pin])
{
isTop[id[i]]=true;
}
else
{
isTop[id[i]]=false;
}
}
}
}
return;
}
void ConvolutionByTop(long long setp)
{
if(setp>=m)return;
for(int l=0,r=0;l<n;l=++r)
{
while(r<n-1&&!isTop[id[r+1]])++r;
int delta=prezero[id[l]];
for(int i=l;i<=r;++i)
{
for(int j=0;j<m;++j)
{
temp[id[i]][j]=a[id[i]][j].get();
}
}
for(int i=l;i<=r;++i)
{
if(delta+setp<m&&temp[id[i]][delta+setp]!=temp[id[l]][delta+setp])
{
long long setpY=(1LL*(temp[id[l]][delta+setp]-temp[id[i]][delta+setp])*Math::inv(temp[id[i]][delta],mod)%mod+mod)%mod;
getKi(setp*setpY,m);
assert(ki[0]!=0);
Poly::NTT(a[id[i]]), Poly::NTT(Ki);
for (int j = 0; j < Poly::lim; ++j) a[id[i]][j] = a[id[i]][j] * Ki[j];
Poly::NTT(a[id[i]], 0);
for (int j = m; j < Poly::lim; ++j)a[id[i]][j]=Int(0);
}
}
}
}
void outPut()
{
int tot=0;
for(int i=0;i<n;++i)
{
tot+=isTop[i];
}
printf("%d\n",tot);
for(int l=0,r=0;l<n;l=++r)
{
while(r<n-1&&!isTop[id[r+1]])++r;
printf("%d\n",r-l+1);
for(int i=l;i<=r;++i)
{
printf("%d%c",id[i],i==r?'\n':' ');
}
}
return;
}
int main()
{
scanf("%d %d %d",&n,&m,&mod);
Poly::init(2*m);
init(1e6);
for(int i=0;i<n;++i)
{
id[i]=i;
bool f=true;
for(int j=0;j<m;++j)
{
scanf("%d",&x);
if(!x&&f)++prezero[i];
else f=false;
a[i][j]=Int(x);
}
}
isTop[0]=true;
//debugger("before");
GroupByPreZero();
for(long long Setp=1;Setp<m;Setp*=mod)
{
GroupByLexicographicalOrder(Setp);
ConvolutionByTop(Setp);
}
GroupByLexicographicalOrder(m);
//debugger("all");
outPut();
return 0;
} 
查看10道真题和解析
投递快手等公司10个岗位 >