题解：SP2883 WIDGET - Widget Factory

· · 题解

好像有锅啊，后面再调吧。

考虑高斯消元求解，每个零件生产的天数为未知数。

题目会给开始时间和结束时间，但没有说中间到底有几周，所以整个方程是 \bmod 7 意义下的，即：

\sum\limits^n_{j=1} s_{1,j}x_1 \equiv d_1 \pmod 7\\ \sum\limits^n_{j=1} s_{2,j}x_2 \equiv d_2 \pmod 7\\ \cdots \\ \sum\limits^n_{j=1} s_{m,j}x_m \equiv d_m \pmod 7 \end{matrix}\right.

其中 s_{i,j} 表示第 i 次记录，第 j 个零件加工了几个，d_i 表示第 i 次加工的时间模 7 意义下的值。

消元时的除法要用逆元。

高斯消元求解完之后我们并没有得到真正的答案，而是：

x_1y_1 \equiv z_1 \pmod 7\\ x_2y_2 \equiv z_2 \pmod 7\\ \cdots \\ x_my_m \equiv z_m \pmod 7 \end{matrix}\right.

所以不能直接输出，需要再求答案。

得益于本题极小的数据范围，这里有若干种方法可供选择，你可以扩欧甚至枚举，这里不过多阐述。

然后是判多解和无解。

如果存在 y_i= 0 且 z_i\not = 0 时为无解。

如果存在 y_i=0 且 z_i=0 时为多解。

这里有个细节，注意到上面有 m 个方程，但未知数只有 n 个，所以多解只判前 n 个即可，但无解需要判断完 m 个方程。

虽然很好想，但这一点卡了我两天。

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<string>
#define sd std::
#define int long long
#define inf 0x3f3f3f3f
#define linf 1e18
#define il inline
#define db double
#define ldb long double
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define f(i,a,b) for(int i=(a);i>=(b);i--)
#define MIN(x,y) (x<y?x:y)
#define MAX(x,y) (x>y?x:y)
#define me(x,y) memset(x,y,sizeof x)
#define pii sd pair<int,int>
//#define umap(x,y) sd unordered_map<x,y>
#define pque(x) sd priority_queue<x>
#define X first
#define Y second
#define kg putchar(' ')
#define Fr(a) for(auto it:a)
#define dbg(x) sd cout<<#x<<": "<<x<<sd endl
il int read(){int w=1,c=0;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) c=(c<<3)+(c<<1)+ch-48;return w*c;}
void printt(int x){if(x>9) printt(x/10);putchar(x%10+48);}
il void print(int x){if(x<0) putchar('-'),printt(-x);else printt(x);}
il void put(int x){print(x);putchar('\n');}
il void printk(int x){print(x);kg;}
const int N=310;
int n,m,k,x;
int a[N][N],ans[N];
sd map<sd string,int> mp;
int ksm(int p,int q)
{
    if(!q) return 1;
    if(q&1) return p*ksm(p,q-1)%7;
    int tmp=ksm(p,q/2)%7;
    return tmp*tmp%7;
}
int ma;
void Guess()
{
    F(i,1,n)
    {
        ma=i;
        F(j,1,m)
        {
            if(a[j][j]&&j<i) continue;
            if(a[j][i]>a[ma][i]) ma=j;
        } 
        F(j,1,n+1) sd swap(a[i][j],a[ma][j]);
        if(!a[i][i]) continue;
        F(j,1,m)
        {
            if(i==j) continue;
            int rate=a[j][i]*ksm(a[i][i],5)%7;
            F(k,i,n+1) a[j][k]=(a[j][k]-rate*a[i][k]%7+7)%7;
        }
    }
}
il void init()
{
    me(a,0);
}
sd string st,en;
il void solve()
{
    init();
    F(i,1,m)
    {
        k=read();
        sd cin>>st>>en;
        F(j,1,k)
        {
            x=read();
            a[i][x]=(a[i][x]+1)%7;
        }
        a[i][n+1]=(mp[en]-(mp[st]-1)+7)%7;
    }
    Guess();
    F(i,1,m) if(!a[i][i]&&a[i][n+1]) return puts("Inconsistent data."),void();
    F(i,1,n) if(!a[i][i]&&!a[i][n+1]) return puts("Multiple solutions."),void();
    F(i,1,n)
    {
        ans[i]=a[i][n+1]*ksm(a[i][i],5)%7;
        if(ans[i]<3) ans[i]+=7;
    }
    F(i,1,n-1) printk(ans[i]);
    put(ans[n]);
}
signed main()
{
    mp["SUN"]=7,mp["MON"]=1,mp["TUE"]=2,mp["WED"]=3,mp["THU"]=4,mp["FRI"]=5,mp["SAT"]=6;
    for(n=read(),m=read();n&&m;solve(),n=read(),m=read());
    return 0;
}