题意是给定一个环，每个位置上有一个数字，问有多少个连续子串满足拼接数字后是给定数字K的倍数 n<=5e4,K<=200,a[i]∈[1,1000] (((也是水题((( 一看K到200就大概知道怎么做了 我的做法比较朴素，先把序列扩展到2n，令p[i]为a[1...i]拼接后模K的值 对于每个i，满足条件的区间为p[i]−p[j−1]∗10i−j%K=0 发现当i加一的时候之前的所有p[j]都要乘10再模K 于是令cnt[i]表示当前满足p[j−1]∗10i−j%K=i的j的个数 每次扫一遍cnt数组，cnt1[i∗10%K]=cnt[i] 当i大于n时要把i−n位置的数字删掉 然后最后的答案要减掉i=n时统计的答案，因为包含在[1,n]的答案会在[n+1,n+n]中再统计一次 O(2nk) 用快速幂T了一发改成预处理10i%K才过了
#include <cstdio> #include <algorithm> #include <iostream> #include <cstring> #include <string> #include <queue> #include <stack> #include <cmath> #include <set> #include <map> #include <bitset> #include <cstdlib> using namespace std; #define pb push_back #define pii pair<int, int> #define mp make_pair #define ull unsigned long long #define null NULL #define PI M_PI #define sc(x) scanf("%d", &x) #define sc64(x) scanf("%I64d", &x) #define scln(x) scanf("%d\n", &x) #define sc64ln(x) scanf("%I64d\n", &x) #define pr(x) printf("%d", x) #define prs(x) printf("x") #define prln(x) printf("%d\n", x) #define prsp(x) printf("%d ", x) #define pr64(x) printf("%I64d", x) #define pr64ln(x) printf("%I64d\n", x) #define pr64sp(x) printf("%I64d ", x) #define rep(i,n) for (int i = 1;i <= (n); ++i) #define repr(i,n) for (int i = (n);i > 0; --i) #define repab(i,a,b) for (int i = a;i <= b; ++i) #define Rep(i,n) for (int i = 0;i < (n); ++i) #define Repr(i,n) for (int i = (n)-1;i >= 0; --i) #define Repab(i,a,b) for (int i = a;i < b; ++i) #define fi first #define se second #define SET(__set, val) memset(__set, val, sizeof __set) typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; template<class T> T gcd(T a, T b){if(!b)return a;return gcd(b,a%b);} template<class T> T power(T a, T b){T res(1);while(b){if(b&1)res=res*a;a=a*a;b>>=1;}return res;} template<class T> T powerM(T a, T b, T mod){T res(1);while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int infi = 2147483647; const ll infl = 9223372036854775807; #define N 111000 #define M 200 int n, m, k, T; int cnt[2][M],a[N],p[N]; int getlen(int x){ int res=0; while(x){ res++,x/=10; } return res; } int shi[N<<1]; int main(){ while (~sc(n)){ sc(k); shi[0] = 1; rep(i,4*n) shi[i] = shi[i-1]*10%k; rep(i,n){ sc(a[i]); a[i+n]=a[i]; } SET(cnt,0); int flag=0; m = 0; ll ans = 0, ans1 = 0; cnt[flag][0] = 1; rep(i,n*2){ int len = getlen(a[i]); if(i<=n)m+=len; p[i] = (p[i-1]*shi[len]+a[i])%k; SET(cnt[flag^1],0); Rep(j,k) if(cnt[flag][j]>0) cnt[flag^1][j*shi[len]%k] += cnt[flag][j]; flag ^= 1; ans += cnt[flag][p[i]]; cnt[flag][p[i]]++; if(i>=n){ int now = shi[m]*p[i-n]%k; cnt[flag][now]--; } if(i==n)ans1 = ans; } pr64ln(ans-ans1); } return 0; }