灌水 (Standard IO)
Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits
Time to Submit: 01:54:23
Description
学生都很喜欢灌水，第一天只有Alice给她的每个朋友灌了一次水，从第二天开始，所有学生（包括Alice）将会有规律地去灌水：
•如果前一天被灌了奇数次的水，他们将会给每个朋友灌一次水；
•如果前一天被灌了偶数次的水，他们将会给每个朋友灌两次水。
学生编号为1到N，Alice为1号，学生之间的朋友关系会给出。
计算H天后一共灌了几次水。
Input
输入一行包含两个整数N和H(1<=N<=20,1<=H<=10^9)，表示学生数和天数。
接下来N行，每行包含N个‘0’或‘1’，（A,B）处的字符表示A和B的关系，‘1’表示是朋友关系，‘0’表示不是。注意自己和自己不是朋友关系，输入保证该矩阵是对称的。
Output
输出H天后一共灌水的数量。
Sample Input
输入1：
4 1
0110
1001
1001
0110
输入2：
4 2
0110
1001
1001
0110
输入3：
5 3
01000
10110
01000
01001
00010
Sample Output
输出1：
2
输出2：
14
输出3：
26
Data Constraint
Hint
【样例解释】
样例2中，第一天Alice灌了2次水，第二天学生1和学生4给学生2和学生3都灌了2次水，而学生2和学生3给学生1和学生4各灌水1次，2天一共灌了12次水。
【数据范围】
50%的数据 H<=1000。
一、暴力（50分）
按照题目说的模拟暴力即可
#include<bits/stdc++.h> using namespace std; inline int poread() { int res = 0; char c = 0; while(!isdigit(c = getchar())); do { res = res * 10 + c - 48; } while(isdigit(c = getchar())); return res; } inline int charget() { char c = 0; while(!isdigit(c = getchar())); return c - 48; } const int MAXN = 25; int mp[MAXN][MAXN]; int jo[MAXN]; long long sum[MAXN]; int n,k; long long ans; int main() { #ifdef lky233 freopen("testdata.in","r",stdin); freopen("testdata.out","w",stdout); #endif n = poread(); k = poread(); for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { mp[i][j] = charget(); } } jo[1] = 1; for(register int kk = 1; kk <= k; ++kk) { memset(sum,0,sizeof(sum)); for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { if(mp[i][j]) sum[j] += jo[i]; } } for(register int i = 1; i <= n; ++i) jo[i] = sum[i] % 2 == 0 ? 2 : 1; for(register int i = 1; i <= n; ++i) ans += sum[i]; cerr<<ans<<endl; } cerr<<ans<<endl; cout<<ans<<endl; }
O(k^2)，五十分。
二、正解
分析数据，一共有n（n<=20）个人，对于每个人有灌别人2次或1次两种状态，一共有2^20 = 1048576种状态，而操作有1e9次，显然会出现重复的状态。
而在这道题中，如果状态重复，一定会陷入循环。（显然）
那么就可以找到这个循环然后快速计算出答案。
#pragma GCC optimize("Ofast") #pragma GCC target("sse3","sse2","sse") //#pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3") //#pragma GCC target("f16c") //#pragma GCC target("fma","avx2") //#pragma GCC target("xop","fma4") #pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector") #pragma GCC diagnostic error "-fwhole-program" #pragma GCC diagnostic error "-fcse-skip-blocks" #pragma GCC diagnostic error "-funsafe-loop-optimizations" #pragma GCC diagnostic error "-std=c++14" #include<bits/stdc++.h> using namespace std; const int MAXN = 25; int mp[MAXN][MAXN]; int n,k; int m; int v[2097160];//2^20 = 2097152; long long sum[100000]; long long sumed[MAXN]; inline int poread() { int res = 0; char c = 0; while(!isdigit(c = getchar())); do { res = res * 10 + c - 48; } while(isdigit(c = getchar())); return res; } inline int charget() { char c = 0; while(!isdigit(c = getchar())); return c - 48; } int main() { #ifdef lky233 freopen("testdata.in","r",stdin); freopen("testdata.out","w",stdout); #endif n = poread(); k = poread(); for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { mp[i][j] = charget(); } } int round = 1; m = 2; for(round; round <= k; ++round) { memset(sumed,0,sizeof(sumed)); for(register int i = 1; i <= n; ++i) { for(register int j = 1; j <= n; ++j) { if(mp[i][j]) { sumed[j] += (m & (1 << i)) ? 1 : 2; } } } if(round == 1) { memset(sumed,0,sizeof(sumed)); for(register int i = 1; i <= n; ++i) sumed[i] += mp[1][i]; } // cerr<<round<<" "<<m<<" "; if(v[m] && v[m] != 1) { break; int ttttt = clock(); while(clock() - ttttt < 2000); } v[m] = round; m = 0; for(register int i = 1; i <= n; ++i) { if(sumed[i] & 1) m = (m | (1<<i)); } for(register int i = 1; i <= n; ++i) sum[round] += sumed[i]; // cerr<<sum[round]<<endl; } // cerr<<endl; round--; long long lsum = 0; long long ans = 0; // cerr<<v[m]<<" "<<round<<endl; //循环区间和 for(register int i = v[m]; i <= round; i++) lsum += sum[i]; //区间段 数 int tim = (k - v[m]) / (round - v[m] + 1); // cerr<<tim<<endl; ans = lsum * tim; //前面的 for(register int i = 1; i <= v[m] - 1; ++i) ans += sum[i]; //剩余的数量 tim = k - tim * (round - v[m] + 1) - v[m] + 1; // cerr<<tim<<endl; //未循环到的区间 for(register int i = v[m]; i <= tim + v[m] - 1; ++i) ans += sum[i]; // cerr<<ans<<endl; cout<<ans<<endl; }
坑点：初始的状态与其他状态不同需要特判。