NC50583. GT 考试
描述
阿申准备报名参加GT考试，准考证号为n位数)
，他不希望准考证号上出现不吉利的数字。
他的不吉利数字)
有m位，不出现是指
中没有恰好一段等于
，
和
可以为0。
他的不吉利数字
输入描述
第一行输入n,m,K，接下来一行输入m位的数。
输出描述
阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果。
示例1
输入:
4 3 100 111
输出:
81
NC50583. GT 考试
描述
输入描述
第一行输入n,m,K，接下来一行输入m位的数。
输出描述
阿申想知道不出现不吉利数字的号码有多少种，输出模K取余的结果。
示例1
输入:
4 3 100 111
输出:
81
Java 解法, 执行用时: 127ms, 内存消耗: 29260K, 提交时间: 2021-08-26 14:28:11
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
public class Main {
static long mod = 1;
static class SegmentTree {
static int l;
static int r;
static long v;
static Node root;
static long cache[];
static void build(long f[]) {
cache = f;
root = new Node(0, f.length - 1);
}
static long query(int left, int right) {
l = left;
r = right;
return root.query();
}
static void add_range(int left, int right, long value) {
l = left;
r = right;
v = value;
v%= mod;
root.add_range();
}
static void multi_range(int left, int right, long value) {
l = left;
r = right;
v = value;
v%= mod;
root.multi_range();
}
static void set_range(int left, int right) {
l = left;
r = right;
// root.set_range();
}
static class Node {
// boolean seted;
long setv = 1;
long add = 0;
int left;
int right;
long min_value;
Node l_node;
Node r_node;
public Node(int l, int r) {
left = l;
right = r;
if (l == r) {
min_value = cache[l]%mod;
} else {
int mid = (l + r) >> 1;
l_node = new Node(l, mid);
r_node = new Node(mid + 1, r);
pollup();
}
}
private long query() {
if (l <= left && r >= right) {
return min_value;
} else if (l > right || r < left) {
return 0;
} else {
pushdown();
long v1 = l_node.query();
long v2 = r_node.query();
pollup();
return (v1+v2)%mod;
}
}
private void add_range() {
if (l <= left && r >= right) {
add += v;
add %= mod;
min_value += v *(right-left+1);
min_value %= mod;
} else if (l > right || r < left) {
return;
} else {
pushdown();
l_node.add_range();
r_node.add_range();
pollup();
}
}
private void multi_range() {
if (l <= left && r >= right) {
setv *= v;
setv %= mod;
add = add*v;
add %= mod;
min_value = (min_value * v) % mod;
} else if (l > right || r < left) {
return;
} else {
pushdown();
l_node.multi_range();
r_node.multi_range();
pollup();
}
}
// private void set_range() {
// if (l <= left && r >= right) {
// seted = true;
// setv = v;
// add = 0;
// min_value = v;
// } else if (l > right || r < left) {
// return;
// } else {
// pushdown();
// l_node.set_range();
// r_node.set_range();
// pollup();
// }
// }
// first multi, then add
private void pushdown() {
if (setv!=1) {
l_node.setv *= setv;
l_node.setv %= mod;
r_node.setv *= setv;
r_node.setv %= mod;
l_node.min_value = l_node.min_value*setv%mod;
r_node.min_value = r_node.min_value*setv%mod;
l_node.add = l_node.add*setv;
l_node.add %= mod;
r_node.add = r_node.add*setv;
r_node.add %= mod;
setv = 1;
}
if (add != 0) {
l_node.add += add;
l_node.add %= mod;
r_node.add += add;
r_node.add %= mod;
l_node.min_value += add * (l_node.right - l_node.left + 1 );
l_node.min_value %= mod;
r_node.min_value += add * (r_node.right - r_node.left + 1 );
r_node.min_value %= mod;
add = 0;
}
}
private void pollup() {
min_value = (l_node.min_value + r_node.min_value)%mod;
}
}
}
static class Task {
public static String roundS(double result, int scale) {
String fmt = String.format("%%.%df", scale);
return String.format(fmt, result);
// DecimalFormat df = new DecimalFormat("0.000000");
// double result = Double.parseDouble(df.format(result));
}
public long gcd(long a,long b){
return b==0?a:gcd(b,a%b);
}
long pm[] = new long[2000001];
boolean f[] = new boolean[2000001];
int p = 0;
public void solve(int testNumber, InputReader in, PrintWriter out) {
for(int j=2;j<=2000000;++j){
if(!f[j]) {
pm[p++] = j;
}
for(int k=0;k<p;++k){
long ck = pm[k] * j;
if(ck>2000000){
break;
}
f[(int)ck] = true;
if(j%pm[k]==0){
break;
}
}
}
// f = new long[1000004];
// rev = new long[1000004];
// f[0] = 1;
// for(int j=1;j<1000003;++j){
// f[j] = f[j-1]*j%mod;
// }
// rev[1000002] = mod_pow(f[1000002],mod-2,mod);
// for(int j=1000001;j>=0;--j){
// rev[j] = rev[j+1] * (j+1) %mod;
// }
// int n = in.nextInt();
// int m = in.nextInt();
// BigInteger c[][] = new BigInteger[513][513];
// // mod =1000;
// for(int j=1;j<=512;++j){
// c[j][0] = c[j][j] = BigInteger.ONE;
// for(int k=1;k<j;++k){
// c[j][k] = c[j-1][k].add( c[j-1][k-1] );
// // c[j][k] %= mod;
// }
// nf[n] = n*(f[n-1] + f[n-2])
// (n-1)*f[n-1] + (n-2)*f[n-2] + f[n-1] + 2*f[n-2];
//
// T[n] = T[n-1] + T[n-2] + f[n-1] + 2*f[n-2];
// S[n] = S[n-1] + T[n];
//
// f[n] = f[n-1] + f[n-2];
// f[n] f[n-1] T[n] T[n-1] S[n]=
int n = in.nextInt();
int m = in.nextInt();
int mod = in.nextInt();
char x[] = in.next().toCharArray();
int l = x.length;
int nxt[] = new int[l+1];
nxt[0] = -1;
int j = 0;
for(int i=1;i<l;++i){
while(j!=-1&&x[i]!=x[j]){
j = nxt[j];
}
nxt[i+1] = ++j;
}
long f[][] = new long[l][l];
for(int st=0;st<l;++st){
for(int num='0';num<='9';++num){
j = st;
while(j!=-1&&x[j]!=num){
j = nxt[j];
}
if(j+1!=l) {
f[st][j + 1] += 1;
}
}
}
long w[][] = new long[1][l];
w[0][0] = 1;
long res[][] = mult(w,mod_pow(f,n,mod),mod);
long y = 0;
for(int i=0;i<l;++i){
y += res[0][i];
y%= mod;
}
out.println(y);
}
long[][] mod_pow(long a[][],int k, long mod){
int n = a.length;
long r[][] = new long[n][n];
long tp[][] = new long[n][n];
for(int i=0;i<n;++i){
r[i][i] = 1;
tp[i] = a[i].clone();
}
while(k>0){
if((k&1)>0){
r = mult(r,tp,mod);
}
tp = mult(tp,tp,mod);
k>>=1;
}
return r;
}
long[][] mult(long a[][],long b[][],long mod){
int n = a.length;
int m = a[0].length;
int k = b[0].length;
long r[][] = new long[n][k];
for(int i=0;i<n;++i){
for(int j=0;j<k;++j){
for(int p=0;p<m;++p){
r[i][j] += a[i][p]%mod*(b[p][j]%mod)%mod;
r[i][j]%= mod;
}
}
}
return r;
}
// long f[];
long rev[];
// long qq(int n,int m){
// f(m==n||m==0) { return 1;}
// return C(n%mod,m%mod);
// }
// long P(int n,int m){
// return f[n]*rev[n-m]%mod;
// }
// long lucas(int n,int m){
// long ans = 1;
// while(n!=0&&m!=0&&ans!=0){
// ans = ans * C((int)(n%mod), (int)(m%mod)) %mod;
// n /= mod;
// m /= mod;
// }
// return ans;
// }
long cc(int f1,int f2){
int tm[] = new int[p];
for(int k=0;k<p;++k){
int c = f1;
while(c>0){
tm[k] += c/pm[k];
c /= pm[k];
}
}
for(int k=0;k<p;++k){
int c = f2;
while(c>0){
tm[k] -= c/pm[k];
c /= pm[k];
}
}
for(int k=0;k<p;++k){
int c = f2+1;
while(c>0){
tm[k] -= c/pm[k];
c /= pm[k];
}
}
long s = 1;
for(int k=0;k<p;++k){
if(tm[k]>0) {
s *= mod_pow(pm[k], tm[k], mod);
s %= mod;
}
}
return s;
}
BigInteger C(long n,long m){
if(n<m) { return BigInteger.ZERO; }
// return f[n]*rev[m]%mod*rev[n-m]%mod;
BigInteger s1 = BigInteger.valueOf(1);
BigInteger s2 = BigInteger.valueOf(1);
for(long j=1;j<=m;++j){
s1 = s1.multiply(BigInteger.valueOf(n-j+1));
s2 = s2.multiply(BigInteger.valueOf(j));
}
BigInteger res= s1.divide(s2);
return res;
}
// int t = in.nextInt();
// int n = in.nextInt();
// int m = in.nextInt();
//
// ct = 0;
// h = new int[n];Arrays.fill(h,-1);
// if(t==1) {
// to = new int[m * 2];
// ne = new int[m * 2];
//
// fob = new boolean[m * 2];
// }else{
// to = new int[m];
// ne = new int[m];
//
// }
//
//
// int rd[] = new int[n];
// int cd[] = new int[n];
// li = new int[m];
// tp = m-1;
//
// int rt= 0;
//
// for(int i=0;i<m;++i){
// int u = in.nextInt()-1;
// int v = in.nextInt()-1;
// add(u,v);
// if(t==1){
// add(v,u);
// }
// cd[u]++;
// rd[v]++;
// rt = u;
// }
//
// if(t==2){
//
// for(int i=0;i<n;++i){
// if(rd[i]!=cd[i]){
// out.println("NO");return;
// }
// }
// }else{
//
// for(int i=0;i<n;++i){
// if(((rd[i]+cd[i])%2)>0){
// out.println("NO");return;
// }
// }
//
// }
//
//
//
// dfs11(rt, t);
//
//
//
// if(tp!=-1){
// out.print("NO");
// return;
// }
//
// out.println("YES");
//
// for(int i=0;i<m;++i){
// out.print(li[i]+ " ");
// }
// int f1[][] = new int[q][3];
//
// for(int i=0;i<q;++i){
// for(int j=0;j<3;++j){
// f1[i][j] = in.nextInt();
// }
// }
//
//
// int h[] = new int[n+1];
//
// Arrays.fill(h,-1);
//
//
// int ne[] = new int[p*2+q];
// int to[] = new int[p*2+q];
// int wt[] = new int[p*2+q];
// ct = 0;
// Func fk = (int x,int y,int z) -> {
// to[ct] = y;
// ne[ct] = h[x];
// wt[ct] = z;
// h[x] = ct++;
// };
//
// for(int i=0;i<p;++i){
// int u = f[i][0];
// int v = f[i][1];
//
//
//
//
// fk.add(u,v,f[i][2]);
// fk.add(v,u,f[i][2]);
// }
//
// for(int i=0;i<q;++i){
// int u = f1[i][0];
// int v = f1[i][1];
//
//
//
//
// fk.add(u,v,f1[i][2]);
// }
// int dp[] = new int[n+1];
// Arrays.fill(dp,100000000);
// dp[s] = 0;
//
//
// PriorityQueue<int[]> qu = new PriorityQueue<>(Comparator.comparingInt((x)->x[0]));
// qu.add(new int[]{0,s});
// while(qu.size()>0){
// int cc[] = qu.poll();
// int cur = cc[1];
// if(cc[0]!=dp[cur]) continue;
// for(int j = h[cur];j!=-1;j=ne[j]){
// int v = to[j];
// if(dp[v] > dp[cur] + wt[j]){
// dp[v] = dp[cur] + wt[j];
// qu.offer(new int[]{dp[v],v});
// }
// }
// }
//
// for(int j=1;j<=n;++j){
// if(dp[j]==100000000){
// out.println("NO PATH");
// }else{
// out.println(dp[j]);
// }
// }
// for(int t=0;t<5;++t) {
// int at = fi[t];
// dp[at][t] = 0;
// PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt((x) -> x[0]));
// q.offer(new int[]{0, at});
// while (q.size() > 0) {
// int cur[] = q.poll();
// if (cur[0] != dp[cur[1]][t]) continue;
// int i = cur[1];
// for (int j = h[i]; j != -1; j = ne[j]) {
// int v = to[j];
// if (dp[i][t] + wt[j] < dp[v][t]) {
// dp[v][t] = dp[i][t] + wt[j];
// q.offer(new int[]{dp[v][t], v});
// }
// }
// }
// }
// int cl[] = new int[]{0,1,2,3,4};
// int rs = Integer.MAX_VALUE;
// do{
// int s= dp[1][cl[0]];
// for(int j=0;j<4;++j){
// int nxt = fi[cl[j+1]];
// s += dp[nxt][cl[j]];
// }
// rs = Math.min(rs,s);
//
//
// }while(next_perm(cl));
//
// out.print(rs);
boolean next_perm(int[] a) {
int len = a.length;
for (int i = len - 2, j = 0; i >= 0; --i) {
if (a[i] < a[i + 1]) {
j = len - 1;
for (; a[j] <= a[i]; --j) ;
int p = a[j];
a[j] = a[i];
a[i] = p;
j = i + 1;
for (int ed = len - 1; j < ed; --ed) {
p = a[ed];
a[ed] = a[j];
a[j++] = p;
}
return true;
}
}
return false;
}
static long mul(long a, long b, long p) {
long res = 0, base = a;
while (b > 0) {
if ((b & 1L) > 0)
res = (res + base) % p;
base = (base + base) % p;
b >>= 1;
}
return res;
}
static long mod_pow(long k, long n, long p) {
long res = 1L;
long temp = k % p;
while (n != 0L) {
if ((n & 1L) == 1L) {
res = mul(res, temp, p);
}
temp = mul(temp, temp, p);
n = n >> 1L;
}
return res % p;
}
public static double roundD(double result, int scale) {
BigDecimal bg = new BigDecimal(result).setScale(scale, RoundingMode.UP);
return bg.doubleValue();
}
}
private static void solve() {
InputStream inputStream = System.in;
// InputStream inputStream = null;
// try {
// inputStream = new FileInputStream(new File("D:\\chrome_download\\exp.out"));
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
OutputStream outputStream = System.out;
// OutputStream outputStream = null;
// File f = new File("D:\\chrome_download\\");
// try {
// f.createNewFile();
// } catch (IOException e) {
// e.printStackTrace();
// }
// try {
// outputStream = new FileOutputStream(f);
// } catch (FileNotFoundException e) {
// e.printStackTrace();
// }
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task task = new Task();
task.solve(1, in, out);
out.close();
}
public static void main(String[] args) {
// new Thread(null, () -> solve(), "1", (1 << 30)).start();
solve();
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String nextLine() {
String line = null;
try {
line = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return line;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public char nextChar() {
return next().charAt(0);
}
public int[] nextArray(int n) {
int res[] = new int[n];
for (int i = 0; i < n; ++i) {
res[i] = nextInt();
}
return res;
}
public long nextLong() {
return Long.parseLong(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
}
}
C++14(g++5.4) 解法, 执行用时: 11ms, 内存消耗: 496K, 提交时间: 2020-02-17 16:20:46
#include<bits/stdc++.h>
using namespace std;
int n, m, K;
string X;
typedef vector<vector<int>> Matrix;
Matrix operator*(const Matrix &A, const Matrix & B) {
Matrix C(A.size(), vector<int>(B[0].size()));
for (size_t i = 0; i < A.size(); i++) {
for (size_t j = 0; j < B[0].size(); j++) {
for (size_t k = 0; k < A[0].size(); k++) (C[i][j]+=1ll* A[i][k] * B[k][j]%K)%=K;
}
}
return C;
}
Matrix powMod(Matrix A, int x) {
Matrix S(A.size(), vector<int>(A.size()));
for (size_t i = 0; i < A.size(); i++) S[i][i] = 1;
while (x) {
if (x % 2) S = S * A;
A = A * A;
x /= 2;
}
return S;
}
int main() {
cin >> n >> m >> K;
cin >> X;
Matrix A(m+1, vector<int>(m+1));
Matrix B(m+1, vector<int>(1));
B[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int ch = '0'; ch <= '9'; ch++) {
if (X[i] == ch) {
if (i + 1 != m) A[i+1][i] = 1;
continue;
}
for (int j = i; j >= 0; j--) {
if (j == 0 || (X[j-1] == ch && X.substr(0, j-1) == X.substr(i-j+1,j-1))) {
A[j][i]++;
break;
}
}
}
}
A = powMod(A, n);
auto C = A * B;
long long tot = 0;
for (auto c: C) (tot += c[0])%=K;
cout << tot << endl;
}
C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 500K, 提交时间: 2020-06-02 11:39:31
#include<bits/stdc++.h>
using namespace std;
int n,m,K;
string X;
typedef vector<vector<int> > Matrix;
Matrix operator*(const Matrix &A,const Matrix &B)
{
Matrix C(A.size(),vector<int>(B[0].size()));
for(size_t i=0;i<A.size();i++)
{
for(size_t j=0;j<B[0].size();j++)
{
for(size_t k=0;k<A[0].size();k++)
(C[i][j]+=1ll*A[i][k]*B[k][j]%K)%=K;
}
}
return C;
}
Matrix powMod(Matrix A,int x)
{
Matrix S(A.size(),vector<int>(A.size()));
for(size_t i=0;i<A.size();i++)
S[i][i]=1;
while(x)
{
if(x%2) S=S*A;
A=A*A;
x/=2;
}
return S;
}
int main()
{
cin>>n>>m>>K;
cin>>X;
Matrix A(m+1,vector<int>(m+1));
Matrix B(m+1,vector<int>(1));
B[0][0]=1;
for(int i=0;i<m;i++)
{
for(int ch='0';ch<='9';ch++)
{
if(X[i]==ch)
{
if(i+1!=m)
A[i+1][i]=1;
continue;
}
for(int j=i;j>=0;j--)
{
if(j==0||(X[j-1]==ch&&X.substr(0,j-1)==X.substr(i-j+1,j-1)))
{
A[j][i]++;
break;
}
}
}
}
A=powMod(A,n);
auto C=A*B;
long long tot=0;
for(auto c:C)
(tot+=c[0])%=K;
cout<<tot<<endl;
}