2018焦作エリア戦ネット予選L:Poor God Water(法則探し+杜教ふるいBM)
5813 ワード
最初はチームメートが手で法則を押して、4まで押して、それからあまりにも煩わしいので、プログラムを書いて時計を打って、それから次の時計を打つプログラムがあります.
サンプルの中で15まであげた时、表を打って15とサンプルが合って、表を打つプログラムは书くべきで何の欠点もありません.
それから何の法則も発見していないで、この時杜教ふるいBMを思い出して、わあ、これは本当にtqlで、前の14項を記入して、すぐに15項目を走り出して、サンプルと合って、それでは、渡して、それからACになりました.
stOドゥー教ふるいBM
#include
using namespace std;
int Bfs(int n)
{
queueque;
while(!que.empty())
que.pop();
que.push("A");
que.push("B");
que.push("C");
int cnt = 0;
while(!que.empty())
{
string s = que.front();
que.pop();
if(s.length() == n)
{
cnt++;
continue;
}
char sss[3];
sss[0] = 'A';
sss[1] = 'B';
sss[2] = 'C';
if(s.length() < 2)
{
for(int i = 0;i < 3; i++)
que.push(s+sss[i]);
continue;
}
for(int i = 0;i < 3; i++)
{
int len = s.size() - 1;
if(sss[i] == 'A' && s[len] == 'A' && s[len-1] == 'A')
continue;
if(sss[i] == 'A' && s[len] == 'C' && s[len-1] == 'B')
continue;
if(sss[i] == 'B' && s[len] == 'C' && s[len-1] == 'A')
continue;
if(sss[i] == 'B' && s[len] == 'B' && s[len-1] == 'B')
continue;
if(sss[i] == 'C' && s[len-1] == 'C')
continue;
que.push(s+sss[i]);
}
}
return cnt;
}
int main()
{
int n;
//freopen("out", "w", stdout);
for(int i = 1;i <= 15; i++)
{
n = i;
cout << Bfs(n) << endl;
}
return 0;
}
サンプルの中で15まであげた时、表を打って15とサンプルが合って、表を打つプログラムは书くべきで何の欠点もありません.
それから何の法則も発見していないで、この時杜教ふるいBMを思い出して、わあ、これは本当にtqlで、前の14項を記入して、すぐに15項目を走り出して、サンプルと合って、それでは、渡して、それからACになりました.
stOドゥー教ふるいBM
#include
#define int long long
using namespace std;
typedef vector VI;
const int mod = 1e9 + 7;
int Powmod(int a, int b) {
int res = 1;
a %= mod;
assert(b >= 0);
for (; b; b >>= 1) {
if (b & 1)
res = res * a % mod;
a = a * a % mod;
}
return res;
}
int _, n;
namespace linear_seq
{
const int N = 10010;
int res[N], base[N], _c[N], _md[N];
vector Md;
void mul(int *a, int *b, int k)
{
for (int i = 0; i < k + k; i++)
_c[i] = 0;
for (int i = 0; i < k; i++)
{
if (a[i])
{
for (int j = 0; j < k; j++)
_c[i + j] = (_c[i + j] + a[i] * b[j]) % mod;
}
}
for (int i = k + k - 1; i >= k; i--)
{
if (_c[i])
{
for(int j = 0;j < Md.size(); j++)
_c[i - k + Md[j]] = (_c[i - k + Md[j]] - _c[i] * _md[Md[j]]) % mod;
}
}
for(int i = 0;i < k; i++)
a[i] = _c[i];
}
int solve(int n, VI a, VI b)
{
int ans = 0, pnt = 0;
int k = a.size();
assert(a.size() == b.size());
for(int i = 0;i < k; i++)
_md[k - 1 - i] = -a[i];
_md[k] = 1;
Md.clear();
for(int i = 0;i < k; i++)
{
if (_md[i] != 0)
Md.push_back(i);
}
for(int i = 0;i < k; i++)
res[i] = base[i] = 0;
res[0] = 1;
while ((1ll << pnt) <= n)
pnt++;
for (int p = pnt; p >= 0; p--)
{
mul(res, res, k);
if ((n >> p) & 1) {
for (int i = k - 1; i >= 0; i--)
res[i + 1] = res[i];
res[0] = 0;
for(int j = 0;j < Md.size(); j++)
res[Md[j]] = (res[Md[j]] - res[k] * _md[Md[j]]) % mod;
}
}
for(int i = 0;i < k; i++)
ans = (ans + res[i] * b[i]) % mod;
if (ans < 0)
ans += mod;
return ans;
}
VI BM(VI s)
{
VI C(1, 1), B(1, 1);
int L = 0, m = 1, b = 1;
for(int n = 0;n < s.size(); n++)
{
int d = 0;
for(int i = 0;i < L + 1; i++)
d = (d + (int)C[i] * s[n - i]) % mod;
if (d == 0)
++m;
else if (2 * L <= n)
{
VI T = C;
int c = mod - d * Powmod(b, mod - 2) % mod;
while (C.size() < B.size() + m)
C.push_back(0);
for(int i = 0;i < B.size(); i++)
C[i + m] = (C[i + m] + c * B[i]) % mod;
L = n + 1 - L;
B = T;
b = d;
m = 1;
}
else
{
int c = mod - d * Powmod(b, mod - 2) % mod;
while (C.size() < B.size() + m)
C.push_back(0);
for(int i = 0;i < B.size(); i++)
C[i + m] = (C[i + m] + c * B[i]) % mod;
++m;
}
}
return C;
}
int gao(VI a, int n)
{
VI c = BM(a);
c.erase(c.begin());
for(int i = 0;i < c.size(); i++)
c[i] = (mod - c[i]) % mod;
return solve(n, c, VI(a.begin(), a.begin() + c.size()));
}
};
signed main()
{
int t;
scanf("%lld", &t);
while (t--)
{
scanf("%lld", &n);
printf("%lld
",
linear_seq::gao(VI{3, 9, 20, 46, 106, 244, 560, 1286, 2956, 6794, 15610, 35866, 82416, 189384}, n - 1));
}
}