本文共 3185 字，大约阅读时间需要 10 分钟。
DP+快速矩阵幂。注意base矩阵的初始化，不难。
1 /* 5564 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 const int mod = 1e9+7; 43 const int maxn = 75; 44 int ID[maxn][maxn]; 45 int n; 46 47 typedef struct mat_t { 48 __int64 m[maxn][maxn]; 49 50 mat_t() { 51 memset(m, 0, sizeof(m)); 52 } 53 54 void init() { 55 memset(m, 0, sizeof(m)); 56 } 57 58 void print() { 59 rep(i, 0, n) { 60 rep(j, 0, n) { 61 printf("%I64d ", m[i][j]); 62 } 63 putchar('\n'); 64 } 65 } 66 } mat_t; 67 68 mat_t matMult(mat_t& a, mat_t& b) { 69 mat_t c; 70 71 rep(i, 0, n) 72 rep(j, 0, n) 73 rep(k, 0, n) 74 c.m[i][j] = (c.m[i][j] + a.m[i][k]*b.m[k][j]%mod)%mod; 75 76 return c; 77 } 78 79 mat_t matPow(mat_t a, int m) { 80 mat_t ret; 81 82 rep(i, 0, n) 83 ret.m[i][i] = 1; 84 while (m) { 85 if (m & 1) 86 ret = matMult(ret, a); 87 a = matMult(a, a); 88 m >>= 1; 89 } 90 91 return ret; 92 } 93 94 mat_t e; 95 mat_t base; 96 97 void init(int s) { 98 // first column is one 99 // first row is zero(accept first one)100 rep(j, 0, n) {101 e.m[0][j] = 0;102 if (j%7 == 1)103 e.m[j][0] = 1;104 else105 e.m[j][0] = 0;106 }107 e.m[0][0] = 1;108 109 rep(i, 0, 10) {110 rep(j, 0, 7) {111 rep(ii, 0, 10) {112 int jj = (10*j+ii)%7;113 int id = ID[i][j];114 int id_ = ID[ii][jj];115 if (i+ii == s)116 e.m[id][id_] = 0;117 else118 e.m[id][id_] = 1;119 }120 }121 }122 123 #ifndef ONLINE_JUDGE124 // e.print();125 #endif126 }127 128 void init_base() {129 int cnt = 1;130 n = 7*10+1;131 132 rep(i, 0, 10)133 rep(j, 0, 7)134 ID[i][j] = cnt++;135 rep(i, 1, 10)136 base.m[0][ID[i][i%7]] = 1;137 }138 139 __int64 cal(int len) {140 if (len == 0)141 return 0;142 143 __int64 ret = 0;144 mat_t res = matPow(e, len);145 146 rep(i, 0, n)147 ret = (ret + base.m[0][i]*res.m[i][0]%mod)%mod;148 return ret;149 }150 151 int main() {152 ios::sync_with_stdio(false);153 #ifndef ONLINE_JUDGE154 freopen("data.in", "r", stdin);155 freopen("data.out", "w", stdout);156 #endif157 158 int t;159 int l, r, s;160 __int64 nl, nr, ans;161 162 init_base();163 scanf("%d", &t);164 while (t--) {165 scanf("%d %d %d", &l, &r, &s);166 init(s);167 nl = cal(l-1);168 nr = cal(r);169 ans = (nr-nl+mod) % mod;170 #ifndef ONLINE_JUDGE171 printf("nl = %I64d, nr = %I64d\n", nl, nr);172 #endif173 printf("%I64d\n", ans);174 }175 176 #ifndef ONLINE_JUDGE177 printf("time = %d.\n", (int)clock());178 #endif179 180 return 0;181 }
转载于:https://www.cnblogs.com/bombe1013/p/4972272.html