20200723T1 【NOIP2015模拟10.28A组】同余

Description

Input

Output

Sample Input

Sample Output

16
0

Data Constraint

solution

日常先打指数暴力dfs水30分

 1 void dfs(int x, int y)
 2 {
 3     if(x == n + 1 && y == 1)
 4     {
 5         int sum = 0;
 6         for(R int i = 1; i <= n; i++)
 7         {
 8             int kkk = 1;
 9             for(R int j = 1; j <= a[i]; j++)
10             {
11                 kkk *= b[i][j];
12             }
13             sum = (sum + kkk) % p;
14         }
15         if(sum == c) ans++, ans %= m ;
16         return;
17     }
18     if(y == a[x])
19     {
20         for(R int i = 0; i < p; i++)
21         {
22             b[x][y] = i;
23             dfs(x + 1, 1);
24             b[x][y] = 0;
25         }
26         return;
27     }
28     for(R int i = 0; i < p; i++)
29     {
30         b[x][y] = i;
31         dfs(x, y + 1);
32         b[x][y] = 0;
33     }
34     return;
35 }
36 signed main()
37 {
38     freopen("congruence.in","r",stdin);
39     freopen("congruence.out","w",stdout);
40     read(t);
41     while(t--)
42     {
43         read(n); read(c); read(p); read(m );
44         ans = 0;
45         for(R int i = 1; i <= n; i++) read(a[i]);
46         dfs(1, 1);
47         writeln(ans);
48     }
49     return 0;
50 }

当n = 1 时

推一下性质

至此已经有50分了

 1 void dfs(int x, int y)
 2 {
 3     if(x == n + 1 && y == 1)
 4     {
 5         int sum = 0;
 6         for(R int i = 1; i <= n; i++)
 7         {
 8             int kkk = 1;
 9             for(R int j = 1; j <= a[i]; j++)
10             {
11                 kkk *= b[i][j];
12             }
13             sum = (sum + kkk) % p;
14         }
15         if(sum == c) ans++, ans %= m ;
16         return;
17     }
18     if(y == a[x])
19     {
20         for(R int i = 0; i < p; i++)
21         {
22             b[x][y] = i;
23             dfs(x + 1, 1);
24             b[x][y] = 0;
25         }
26         return;
27     }
28     for(R int i = 0; i < p; i++)
29     {
30         b[x][y] = i;
31         dfs(x, y + 1);
32         b[x][y] = 0;
33     }
34     return;
35 }
36 int ksm (int x,int y)
37 {
38     int res = 1;
39     while(y)
40     {
41         if(y & 1) res = res * x % m ;
42         x = x * x % m ;
43         y >>= 1;
44     }
45     return res;
46 }
47 signed main()
48 {
49     freopen("congruence.in","r",stdin);
50     freopen("congruence.out","w",stdout);
51     read(t);
52     while(t--)
53     {
54         read(n); read(c); read(p); read(m );
55         ans = 0;
56         for(R int i = 1; i <= n; i++) read(a[i]);
57         if(n == 1)
58         {
59             if(c != 0) writeln( ksm (p - 1, a[1] - 1));
60             else writeln( (ksm (p, a[1]) - ksm (p - 1, a[1]) + m ) % m );
61             continue;
62         }
63         dfs(1, 1);
64         writeln(ans);
65     }
66     return 0;
67 }

先挖坑，A了再来

————————————————————————————————————————分界线

要吐了。。

每运算一次都要取模！！！！！！

不然会炸。。。

code的思路是另一种

——转自mlg%%%

记得取模

code

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<queue>
 7 #include<vector>
 8 #include<stack>
 9 #include<set>
10 #include<deque>
11 #include<map>
12 using namespace std;
13 
14 template <typename T> void read(T &x) {
15     x = 0; int f = 1; char c;
16     for (c = getchar(); c < '0' || c > '9'; c = getchar()) if (c == '-') f = -f;
17     for (; c >= '0' && c <= '9'; c = getchar()) x = 10 * x + c - '0' ;
18     x *= f;
19 }
20 template <typename T> void write(T x){
21     if (x < 0) putchar('-'), x = -x;
22     if (x > 9) write(x / 10);
23     putchar(x % 10 + '0');
24 }
25 template <typename T> void writeln(T x) { write(x); putchar('
'); }
26 template <typename T> void writesn(T x) { write(x); putchar(' '); }
27 
28 #define int long long
29 #define inf 1234567890
30 #define next net
31 #define P 1000000007
32 #define N 50
33 #define mid ((l+r)>>1)
34 #define lson (o<<1)
35 #define rson (o<<1|1)
36 #define R register
37 
38 int t, n, c, p, m ;
39 int a;
40 int a1,a2,b1,b2,ansa,ansb;
41 int ksm (int x,int y)
42 {
43     int res = 1;
44     while(y)
45     {
46         if(y & 1) res = res * x % m ;
47         x = x * x % m ;
48         y >>= 1;
49     }
50     return res;
51 }
52 inline int modd(int x)
53 {
54     x = (x % m + m ) % m ;
55     return x;
56 }
57 signed main()
58 {
59     //freopen("congruence.in","r",stdin);
60     //freopen("congruence.out","w",stdout);
61     read(t);
62     while(t--)
63     {
64         read(n); read(c); read(p); read(m );
65         read(a);
66         ansa = a1 = a2 = modd(ksm(p - 1, a - 1));
67         ansb = b1 = b2 = modd(ksm(p, a) - ksm(p - 1, a));
68         for(R int i = 1; i < n; i++)
69         {
70             read(a);
71             a1 = modd(ksm(p - 1, a - 1));
72             b1 = modd(ksm(p, a) - ksm(p - 1, a)); 
73             a2 = ansa; b2 = ansb;
74             ansa = modd(modd(b1 * a2) + modd(b2 * a1) + modd(modd((p - 2) * a1) * a2));
75             ansb = modd(modd(b1 * b2) + modd(modd((p - 1) * a1) * a2));
76         }
77         if(c == 0) writeln(ansb);
78         else writeln(ansa);
79     }
80     return 0;
81 }