題目描述

小 C 喜歡跑步，并且非常喜歡在微信步數(shù)排行榜上刷榜，為此他制定了一個(gè)刷微信步數(shù)的計(jì)劃。

他來到了一處空曠的場(chǎng)地，處于該場(chǎng)地中的人可以用?kk?維整數(shù)坐標(biāo)?(a1,a2,…,ak)(a1,a2,…,ak)?來表示其位置。場(chǎng)地有大小限制，第?ii?維的大小為?wiwi，因此處于場(chǎng)地中的人其坐標(biāo)應(yīng)滿足?1≤ai≤wi1≤ai≤wi（1≤i≤k1≤i≤k）。

小 C 打算在接下來的?P=w1×w2×?×wkP=w1×w2×?×wk?天中，每天從場(chǎng)地中一個(gè)新的位置出發(fā)，開始他的刷步數(shù)計(jì)劃（換句話說，他將會(huì)從場(chǎng)地中每個(gè)位置都出發(fā)一次進(jìn)行計(jì)劃）。

他的計(jì)劃非常簡(jiǎn)單，每天按照事先規(guī)定好的路線行進(jìn)，每天的路線由?nn?步移動(dòng)構(gòu)成，每一步可以用?cici?與?didi?表示：若他當(dāng)前位于?(a1,a2,…,aci,…,ak)(a1,a2,…,aci,…,ak)，則這一步他將會(huì)走到?(a1,a2,…,aci+di,…,ak)(a1,a2,…,aci+di,…,ak)，其中?1≤ci≤k1≤ci≤k，di∈{?1,1}di∈{?1,1}。小 C 將會(huì)不斷重復(fù)這個(gè)路線，直到他走出了場(chǎng)地的范圍才結(jié)束一天的計(jì)劃。（即走完第?nn?步后，若小 C 還在場(chǎng)內(nèi)，他將回到第?11?步從頭再走一遍）。

小 C 對(duì)自己的速度非常有自信，所以他并不在意具體耗費(fèi)的時(shí)間，他只想知道?PP?天之后，他一共刷出了多少步微信步數(shù)。請(qǐng)你幫他算一算。

輸入格式

第一行兩個(gè)用單個(gè)空格分隔的整數(shù)?n,kn,k。分別表示路線步數(shù)與場(chǎng)地維數(shù)。

接下來一行?kk?個(gè)用單個(gè)空格分隔的整數(shù)?wiwi，表示場(chǎng)地大小。

接下來?nn?行每行兩個(gè)用單個(gè)空格分隔的整數(shù)?ci,dici,di，依次表示每一步的方向，具體意義見題目描述。

輸出格式

僅一行一個(gè)整數(shù)表示答案。答案可能很大，你只需要輸出其對(duì)?109+7109+7?取模后的值。

若小 C 的計(jì)劃會(huì)使得他在某一天在場(chǎng)地中永遠(yuǎn)走不出來，則輸出一行一個(gè)整數(shù)??1?1。

樣例數(shù)據(jù)

3 2 3 3 1 1 2 -1 1 1 21 5 4 6 8 6 5 3 1 2 1 1 1 2 1 2 -1 10265 5 5 3 3 1 3 2 4 1 4 -1 1 -1 3 -1 2 1 150 100 3 8 7 6 1 1 1 -1 3 1 3 -1 3 1 3 -1 3 1 3 -1 1 1 1 -1 1 1 1 -1 2 1 2 -1 1 1 1 -1 2 1 2 -1 3 1 3 -1 3 1 3 -1 3 1 3 -1 2 1 2 -1 3 1 3 -1 3 1 3 -1 1 1 1 -1 1 1 1 -1 3 1 3 -1 3 1 3 -1 1 1 1 -1 1 1 1 -1 2 1 2 -1 1 1 1 -1 2 1 2 -1 2 1 2 -1 2 1 2 -1 3 1 3 -1 1 1 1 -1 3 1 3 -1 3 1 3 -1 3 1 3 -1 3 1 3 -1 1 1 1 -1 3 1 3 -1 1 1 1 -1 2 1 2 -1 1 1 1 -1 1 1 1 -1 2 1 2 -1 2 1 2 -1 1 1 1 -1 3 1 3 -1 1 1 1 -1 2 1 2 -1 1 1 1 -1 3 1 3 -1 3 1 3 -1 3 1 3 -1 2 1 2 -1 3 1 3 -1 -1

數(shù)據(jù)范圍

【樣例 #1 解釋】

從?(1,1)(1,1)?出發(fā)將走?22?步，從?(1,2)(1,2)?出發(fā)將走?44?步，從?(1,3)(1,3)?出發(fā)將走?44?步。

從?(2,1)(2,1)?出發(fā)將走?22?步，從?(2,2)(2,2)?出發(fā)將走?33?步，從?(2,3)(2,3)?出發(fā)將走?33?步。

從?(3,1)(3,1)?出發(fā)將走?11?步，從?(3,2)(3,2)?出發(fā)將走?11?步，從?(3,3)(3,3)?出發(fā)將走?11?步。

共計(jì)?2121?步。

【數(shù)據(jù)范圍】

測(cè)試點(diǎn)編號(hào)n≤n≤k≤k≤wi≤wi≤

1～31～3	55	55	33
4～64～6	100100	33	1010
7～87～8	105105	11	105105
9～129～12	105105	22	106106
13～1613～16	5×1055×105	1010	106106
17～2017～20	5×1055×105	33	109109

對(duì)于所有測(cè)試點(diǎn)，保證?1≤n≤5×1051≤n≤5×105，1≤k≤101≤k≤10，1≤wi≤1091≤wi≤109，di∈{?1,1}di∈{?1,1}。

#include <bits/stdc++.h> #define rep(i, a, b) for (int i = (a); i <= int(b); i++) #define per(i, a, b) for (int i = (a); i >= int(b); i--) using namespace std;typedef long long ll; const int maxn = 5e5, mod = 1e9 + 7;int n, k, w[10], c[maxn + 5], d[maxn + 5], dt[10], res, S[11][11], inv[12];struct foo {int z[10], l[10], r[10];void reset() {memset(z, 0, k << 2);memset(l, 0, k << 2);memset(r, 0, k << 2);}foo() {reset();}int walk(int c, int d) {z[c] += d;if (z[c] < l[c] || z[c] > r[c]) {l[c] = min(l[c], z[c]);r[c] = max(r[c], z[c]);return d;}return 0;} } F, B;inline void red(int &x) {x += x >> 31 & mod; }void prework(int n) {S[0][0] = 1;rep(i, 1, n) rep(j, 1, i) {S[i][j] = (S[i - 1][j - 1] + ll(S[i - 1][j]) * j) % mod;}inv[1] = 1;rep(i, 2, n + 1) {inv[i] = ll(mod - mod / i) * inv[mod % i] % mod;} }int calc(int k, int n) {int s = 0, c = 1;rep(i, 0, k) {c = ll(c) * max(0, n - i) % mod;s = (s + ll(c) * inv[i + 1] % mod * S[k][i]) % mod;}return s; }int work(int a[]) {int lim = mod;rep(i, 0, k - 1) if (dt[i]) {lim = min(lim, (a[i] + dt[i] - 1) / dt[i]);}int dp[11] = { 1 };rep(i, 0, k - 1) {per(j, i, 0) {dp[j + 1] = (dp[j + 1] + ll(mod - dt[i]) * dp[j]) % mod;dp[j] = ll(a[i]) * dp[j] % mod;}}int res = 0;rep(i, 0, k) {res = (res + ll(dp[i]) * calc(i, lim)) % mod;}return res; }int main() {scanf("%d %d", &n, &k);prework(k);rep(i, 0, k - 1) {scanf("%d", &w[i]);}rep(i, 1, n) {scanf("%d %d", &c[i], &d[i]), c[i]--;if (F.walk(c[i], d[i]) && F.r[c[i]] - F.l[c[i]] <= w[c[i]]) {int x = 1;rep(j, 0, k - 1) if (j != c[i]) {x = ll(x) * max(0, w[j] - F.r[j] + F.l[j]) % mod;}res = (res + ll(i) * x) % mod;}}rep(i, 1, n) if (F.z[c[i]] < 0) {d[i] = -d[i];}rep(i, 0, k - 1) if (F.z[i] < 0) {F.z[i] = -F.z[i];swap(F.l[i], F.r[i]);F.l[i] = -F.l[i];F.r[i] = -F.r[i];}B = F;bool chk = true;rep(i, 0, k - 1) {dt[i] = B.z[i];chk &= dt[i] == 0;}if (chk) {bool ok = false;rep(i, 0, k - 1) {ok |= B.r[i] - B.l[i] >= w[i];}printf("%d\n", ok ? res : -1);exit(0);}int a[10] = {};rep(i, 1, n) {if (F.walk(c[i], d[i]) && F.r[c[i]] - F.l[c[i]] <= w[c[i]]) {bool ok = true;rep(j, 0, k - 1) if (j != c[i]) {ok &= w[j] - F.r[j] + F.l[j] > 0;}if (!ok) {continue;}rep(j, 0, k - 1) if (j != c[i]) {a[j] = w[j] - F.r[j] + F.l[j];}a[c[i]] = w[c[i]] - F.r[c[i]] + F.l[c[i]] + 1, res = (res + ll(i) * work(a)) % mod;a[c[i]] = w[c[i]] - F.r[c[i]] + F.l[c[i]], res = (res + ll(mod - i) * work(a)) % mod;}}rep(i, 0, k - 1) {a[i] = max(0, w[i] - B.r[i] + B.l[i]);}res = (res + ll(n) * work(a)) % mod;printf("%d\n", res);return 0; }

總結(jié)

以上是生活随笔為你收集整理的微信步数C++的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。