Vasya and Shifts

题目描述

Vasya has a set of $4n$ strings of equal length, consisting of lowercase English letters “a”, “b”, “c”, “d” and “e”. Moreover, the set is split into $n$ groups of $4$ equal strings each. Vasya also has one special string $a$ of the same length, consisting of letters “a” only.

Vasya wants to obtain from string $a$ some fixed string $b$, in order to do this, he can use the strings from his set in any order. When he uses some string $x$, each of the letters in string $a$ replaces with the next letter in alphabet as many times as the alphabet position, counting from zero, of the corresponding letter in string $x$. Within this process the next letter in alphabet after “e” is “a”.

For example, if some letter in $a$ equals “b”, and the letter on the same position in $x$ equals “c”, then the letter in $a$ becomes equal “d”, because “c” is the second alphabet letter, counting from zero. If some letter in $a$ equals “e”, and on the same position in $x$ is “d”, then the letter in $a$ becomes “c”. For example, if the string $a$ equals “abcde”, and string $x$ equals “baddc”, then $a$ becomes “bbabb”.

A used string disappears, but Vasya can use equal strings several times.

Vasya wants to know for $q$ given strings $b$, how many ways there are to obtain from the string $a$ string $b$ using the given set of $4n$ strings? Two ways are different if the number of strings used from some group of $4$ strings is different. Help Vasya compute the answers for these questions modulo $10^9+7$.

题意概述

给定$n$个长度为$m$的五进制数，每个数字最多用四次。定义两个五进制数的加法运算为按位相加后各位对五取模（无进位）。现有$q$组询问，每组询问给定一个长度为$m$的五进制数，求用前面的五进制数相加得到此数的方案数。

数据范围：$1 \le n, m \le 500, \ 1 \le q \le 300$。

算法分析

题目定义的这种加法类似于二进制下的异或运算。容易想到线性基。线性基是一种特殊的基，它通常会在异或运算中出现，它的意义是：通过原集合$S$的某一个最小子集$S_1$使得$S_1$内元素相互异或得到的值域与原集合$S$相互异或得到的值域相同。可以用高斯消元求线性基。对于每一组询问，判断是否可以由线性基相加得到，如果不能则输出$0$，否则方案数为$5^{n-|S_1|}$。

代码

#include <iostream>
#include <cstring>
using namespace std;
const long long mod = 1000000007ll;
long long n, m, q, a[501][501], b[501][501], r[501], p[501], t, ans = 1;
bool vis[501];
string s;
void gauss() {
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j)
      if (a[i][j])
        if (!vis[j]) {
          vis[j] = true, ++t;
          for (int k = 1; k <= m; ++k) b[j][k] = a[i][k];
          break;
        } else {
          int t = 0;
          while (a[i][j]) (a[i][j] += b[j][j]) %= 5, ++t;
          for (int k = 1; k <= m; ++k)
            if (j != k) (a[i][k] += b[j][k] * t) %= 5;
        }
}
int main()
{
  cin >> n >> m, ans = 1;
  for (int i = 1; i <= n; ++i) {
    cin >> s;
    for (int j = 1; j <= m; ++j) a[i][j] = s[j - 1] - 'a';
  }
  cin >> q, gauss();
  for (int i = t; i < n; ++i) (ans *= 5) %= mod;
  while (q--) {
    cin >> s, memset(p, 0, sizeof p);
    for (int i = 1; i <= m; ++i) r[i] = s[i - 1] - 'a';
    bool flag = false;
    for (int i = 1; i <= m; ++i) {
      if (p[i] != r[i]) {
        if (!b[i][i]) { flag = true; break; }
        int t = 0;
        while (p[i] != r[i]) (p[i] += b[i][i]) %= 5, ++t;
        for (int j = 1; j <= m; ++j)
          if (i != j) (p[j] += b[i][j] * t) %= 5;
      }
    }
    if (flag) cout << 0 << endl;
    else cout << ans << endl;
  }
  return 0;
}